3709: [PA2014]Bohater
Time Limit: 5 Sec Memory Limit: 128 MBSec Special Judge
Submit: 648 Solved: 218
[Submit][Status][Discuss]
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
3 1
4 8
8 3
Sample Output
TAK
2 3 1
2 3 1
HINT
Source
贪心算法。。
我们把怪物分成两种一种是打完可以加血的。。。一种是打完会少血的。。。
显然我们应该先打可以加血的。。。再打会少血的。。。
对于可以加血的。。。我们将它按照消耗从小到大排序。。。可以自己想一下。。这个是显然可以的。。。
对于会少血的。。。我们可以倒过来考虑排序方式。。。就相当于我们把吃下去的血瓶吐出来然后再加上消耗的血。。。这就和第一种一样了。。。然后倒过来就是我们要的排序方式。。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
struct data{int d,a,id;} a[N],b[N];
long long n,z,x,y,s1,s2;
int read(){
int x = 0,f = 1,c = getchar();
while (c<'0' || c>'9'){if (c=='-') f = -1;c = getchar();}
while (c>='0' && c<='9') x = x*10+c-'0',c = getchar();
return x*f;
}
bool cmpa(data a,data b){return a.d<b.d;}
bool cmpb(data a,data b){return a.a>b.a;}
int main(){
n = read();scanf("%lld",&z);
for (int i=1;i<=n;i++){
x = read();y = read();
if (x<=y) a[++s1] = (data){x,y,i};
else b[++s2] = (data){x,y,i};
}
sort(a+1,a+1+s1,cmpa);
for (int i=1;i<=s1;i++)
if (z<=a[i].d) {return printf("NIE"),0;}
else z = z-a[i].d+a[i].a;
sort(b+1,b+1+s2,cmpb);
for (int i=1;i<=s2;i++)
if (z<=b[i].d) {return printf("NIE"),0;}
else z = z-b[i].d+b[i].a;
printf("TAK\n");
for (int i=1;i<=s1;i++) printf("%d ",a[i].id);
for (int i=1;i<=s2;i++) printf("%d ",b[i].id);
}
评论 (0)
