bzoj3709 [PA2014]Bohater

Description

在一款电脑游戏中，你需要打败n只怪物（从1到n编号）。为了打败第i只怪物，你需要消耗d[i]点生命值，但怪物死后会掉落血药，使你恢复a[i]点生命值。任何时候你的生命值都不能降到0（或0以下）。请问是否存在一种打怪顺序，使得你可以打完这n只怪物而不死掉

Input

第一行两个整数n,z(1<=n,z<=100000)，分别表示怪物的数量和你的初始生命值。
接下来n行，每行两个整数d[i],a[i](0<=d[i],a[i]<=100000)

Output

第一行为TAK（是）或NIE（否），表示是否存在这样的顺序。
如果第一行为TAK，则第二行为空格隔开的1~n的排列，表示合法的顺序。如果答案有很多，你可以输出其中任意一个。

Sample Input

3 5
3 1
4 8
8 3

Sample Output

TAK
2 3 1

正解：贪心。

首先，先打回血的肯定比先打扣血的好。

然后打回血的，肯定是先打扣血少的更优。

再看打扣血的，可以发现，这是前面这个操作的逆过程，所以先打回血多的就好了。

1 #include <bits/stdc++.h>
 2 #define il inline
 3 #define RG register
 4 #define ll long long
 5 
 6 using namespace std;
 7 
 8 struct data{ int i; ll d,a; }q[100010];
 9 
10 int n,tot;
11 ll k;
12 
13 il ll gi(){
14   RG ll x=0,q=1; RG char ch=getchar();
15   while ((ch<'0' || ch>'9') && ch!='-') ch=getchar();
16   if (ch=='-') q=-1,ch=getchar();
17   while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar();
18   return q*x;
19 }
20 
21 il int cmp1(const data &x,const data &y){ return x.a-x.d>y.a-y.d; }
22 il int cmp2(const data &x,const data &y){ return x.d<y.d; }
23 il int cmp3(const data &x,const data &y){ return x.a>y.a; }
24 
25 int main(){
26 #ifndef ONLINE_JUDGE
27   freopen("Bohater.in","r",stdin);
28   freopen("Bohater.out","w",stdout);
29 #endif
30   cin>>n>>k;
31   for (RG int i=1;i<=n;++i) q[i].i=i,q[i].d=gi(),q[i].a=gi();
32   sort(q+1,q+n+1,cmp1);
33   for (RG int i=1;i<=n;++i) if (q[i].a>q[i].d) tot=i; else break;
34   if (tot) sort(q+1,q+tot+1,cmp2);
35   if (tot<n) sort(q+tot+1,q+n+1,cmp3);
36   for (RG int i=1;i<=n;++i){
37     k-=q[i].d; if (k<=0) puts("NIE"),exit(0); k+=q[i].a;
38   }
39   puts("TAK");
40   for (RG int i=1;i<=n;++i) printf("%d ",q[i].i); return 0;
41 }