【GDOI2016模拟4.5】刺客 题解

【GDOI2016模拟4.5】刺客

Description

SillyHook是一个著名的刺客,虽然他比较Silly,但他精通打洞,善于深入敌方内部刺杀敌人。
现在SillyHook接到了若干个消灭敌人的任务,每次任务中他都会装备一把耐久度为m 的钩刃,并打洞潜入敌方内部。有n 个待消灭的敌人SillyHook消灭第i 个敌人需要消耗钩刃Ai 点耐久度(如果有其他武器则可以选择用其他武器消灭这个敌人,且不消耗钩刃耐久度),之后便得到他的武器,可以用来消灭任意Bi 个敌人。但SillyHook太Silly了,请你帮他求出每次任务最多可以消灭多少个敌人,且在消灭敌人数量最多的前提下使钩刃消耗的耐久度最少。
注意每次任务之间互不影响。

Input

第一行一个整数T,表示有T次任务。
对于每组数据,第一行包含两个正整数n,m 表示目标数和钩刃的初始耐久度。
接下来n 行每行两个正整数Ai,Bi ,意义如题目所述。

Output

每次任务一行两个整数,表示这次任务中最多能消灭的敌人数量,以及钩刃最少消耗的耐久度。

Sample Input

2
3 5
4 1
5 1
7 7
2 1
2 2
4 0

Sample Output

3 4
0 0

Data Constraint

30%的数据满足Bi=0 。
存在20% 的数据满足n<=10 。
100%的数据满足T<=10,1<=n<=105,1<=m<=109,0<=Ai<=109,0<=Bi<=10。

题解

首先这题显然是贪心。
先讲讲我考场上错误的思路,就是首先舍弃一部分耐久杀掉一个有刀且Ai最小的敌人(如果有刀且 A [ i ] A[i] A[i]最小的敌人的 A [ i ] > m A[i]>m A[i]>m那么就把只能所有人敌人当作 B [ i ] = 0 B[i]=0 B[i]=0的杀了,也就是直接从小到大杀),之后再用拿到的刀按Ai从大到小杀剩下有刀的敌人,再拿总共拿到的刀按Ai从大到小杀完刀的次数,然后拿最后剩的耐久再按Ai从小到大杀。
这个思路不认真想想真的发现不了什么问题,但是大家看一看这组数据:
1
4 100
1 1
1 1
100 0
100 0
用上述方法模拟一下会发现只能杀掉3个敌人,但实际上是可以4个全部杀掉的,只需要用耐久把第一和第二个敌人杀掉就可以了。
那么上述方法的问题出在哪呢?
没错就是我们没有“留刀”这一操作。
于是我们考虑怎么执行我们这个“留刀”操作。
首先我们先舍弃一部分耐久杀掉一个有刀且 A [ i ] A[i] A[i]最小的敌人是没有错的,显然这必定最优的一步。
之后我们把 ∑ B [ i ] \sum{B[i]} ∑B[i](设为 s u m sum sum)统计出来,也就是代表用敌人的刀可以杀掉多少个敌人,然后分两类讨论:
1.如果 s u m > = n sum>=n sum>=n,也就是说可以全部使用敌人的刀把敌人杀完
2.如果 s u m < n sum<n sum<n,也就是说不能全部使用敌人的刀把敌人杀完,于是我们就可以执行“留刀”操作,把敌人的刀用来杀那些 A [ i ] A[i] A[i]较大的敌人,之后再用剩下的耐久从小到大杀就行了

CODE

#include<cstdio>
#include<string>
#include<algorithm>
#define max(a,b) (((a)>(b))?(a):(b))
#define min(a,b) (((a)<(b))?(a):(b))
#define R register int
#define N 100005
#define ll long long
using namespace std;
struct arr{int a,b;}x[N];
int t,n,m,ans1,ans2;
inline void read(int &x)
{
	x=0;int f=1;char ch=getchar();
	while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();x*=f;
}
inline bool cmp(arr x,arr y) {return x.a<y.a;}
int main()
{
	read(t);
	while (t--)
	{
		read(n);read(m);ans1=ans2=0;
		for (R i=1;i<=n;++i) read(x[i].a),read(x[i].b);
		sort(x+1,x+1+n,cmp);int first=0;
		for (R i=1;i<=n;++i)
			if (x[i].b) {first=i;break;}
		int tot=0;
		if (first && x[first].a<=m)
		{
			ans2=x[first].a;ans1=x[first].b+1;
			for (R i=1;i<=n;++i)
				if (i!=first) ans1+=x[i].b;
		}
		else first=0;
		if (ans1>=n) printf("%d %d\n",n,ans2);
		else
		{
			for (R i=1;i<=n;++i)
			{
				if (x[i].a+ans2>m || ans1>=n) break;
				if (i!=first) ++ans1,ans2+=x[i].a;
			}
			printf("%d %d\n",ans1,ans2);
		}
	}
	return 0;
}
上一篇:工作中的坑(1) securerandom


下一篇:关于SourceRandom的使用