「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
3 1
4 8
8 3
Sample Output
TAK
2 3 1
2 3 1
题解
首先，先把杀掉能回血的先杀了
显然杀的顺序按照消耗升序
杀完以后，不管用什么顺序杀掉剩下的怪，最后体力last是确定的
倒序来看，相当于将血药吐出来然后返还杀怪的消耗，那么显然也是按照损失体力（即血药回血量）升序，正回来即是降序。。。
即分为两部分，杀完能回血的按照消耗升序，剩余按血药回血量降序，然后模拟一遍判断是否合法即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,t1,t2; ll z; struct data{int d,a,id;}a[100005],b[100005]; bool cmp1(data a,data b) { return a.d<b.d; } bool cmp2(data a,data b) { return a.a>b.a; } int main() { n=read();z=read(); for(int i=1;i<=n;i++) { int x=read(),y=read(); if(x<=y)a[++t1].d=x,a[t1].a=y,a[t1].id=i; else b[++t2].d=x,b[t2].a=y,b[t2].id=i; } sort(a+1,a+t1+1,cmp1); for(int i=1;i<=t1;i++) if(z<=a[i].d){puts("NIE");return 0;} else z=z-a[i].d+a[i].a; sort(b+1,b+t2+1,cmp2); for(int i=1;i<=t2;i++) if(z<=b[i].d){puts("NIE");return 0;} else z=z-b[i].d+b[i].a; puts("TAK"); for(int i=1;i<=t1;i++) printf("%d ",a[i].id); for(int i=1;i<=t2;i++) printf("%d ",b[i].id); return 0; } |
Subscribe
计数器 9787224
OI 课件=>
OI 课件=>