为了打败第i只怪物

作者:单机电脑游戏排行榜

Description

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

Input

为了打败第i只怪物。第一行两个整数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

 

题解:

这题可以分成两个部分,就是杀完回复血量更多的,和杀完损失血量更多的。

我们应该优先那回复血量更多的,用击杀时损失血量升序排,这样保证稳定上升。

后者就是应该损失血量较小的先,这样就ok了。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<algorithm>
 6 #include<cmath>
 7 #define ll long long 
 8 using namespace std;
 9 int n,t1,t2;
10 ll z;
11 struct data{int d,a,id;}a[100005],b[100005];
12 bool cmp1(data a,data b)
13 {
14     return a.d<b.d;
15 }
16 bool cmp2(data a,data b)
17 {
18     return a.a>b.a;
19 }
20 int main()
21 {
22     scanf("%d%d",&n,&z);
23     int x,y;
24     for(int i=1;i<=n;i++)
25     {
26         scanf("%d%d",&x,&y);
27         if(x<=y)a[++t1].d=x,a[t1].a=y,a[t1].id=i;
28         else b[++t2].d=x,b[t2].a=y,b[t2].id=i;
29     }
30     sort(a+1,a+t1+1,cmp1);
31     for(int i=1;i<=t1;i++)
32         if(z<=a[i].d){puts("NIE");return 0;}
33         else z=z-a[i].d+a[i].a;
34     sort(b+1,b+t2+1,cmp2);
35     for(int i=1;i<=t2;i++)
36         if(z<=b[i].d){puts("NIE");return 0;}
37         else z=z-b[i].d+b[i].a;
38     puts("TAK");
39     for(int i=1;i<=t1;i++)
40         printf("%d ",a[i].id);
41     for(int i=1;i<=t2;i++)
42         printf("%d ",b[i].id);
43 }

 

本文由澳门新葡亰平台游戏发布,转载请注明来源

关键词: