首页 > 代码库 > BZOJ3709: [PA2014]Bohater

BZOJ3709: [PA2014]Bohater

2024-07-26 00:13:27   214人阅读

3709: [PA2014]Bohater

Time Limit: 5 Sec  Memory Limit: 128 MBSec  Special Judge
Submit: 339  Solved: 109
[Submit][Status]

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

HINT

Source

鸣谢Jcvb

题解：
刚开始贪心贪错了，以为扣血的应该按扣血量从大往小打，不然现在不打扣了血怎么打。。。
然后发现了这个反例：
5滴血，一只扣3血回3血，一只扣4血回0……
T_T
忘记现在能打的情况了。。。
hzwer：
倒序来看，相当于将血药吐出来然后返还杀怪的消耗，那么显然也是按照损失体力（即血药回血量）升序，正回来即是降序。。。
代码：
  1 #include<cstdio>  2   3 #include<cstdlib>  4   5 #include<cmath>  6   7 #include<cstring>  8   9 #include<algorithm> 10  11 #include<iostream> 12  13 #include<vector> 14  15 #include<map> 16  17 #include<set> 18  19 #include<queue> 20  21 #include<string> 22  23 #define inf 1000000000 24  25 #define maxn 100005 26  27 #define maxm 500+100 28  29 #define eps 1e-10 30  31 #define ll long long 32  33 #define pa pair<int,int> 34  35 #define for0(i,n) for(int i=0;i<=(n);i++) 36  37 #define for1(i,n) for(int i=1;i<=(n);i++) 38  39 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 40  41 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 42  43 #define mod 1000000007 44  45 using namespace std; 46  47 inline int read() 48  49 { 50  51     int x=0,f=1;char ch=getchar(); 52  53     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 54  55     while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 56  57     return x*f; 58  59 } 60 int n,l,r; 61 struct rec{int x,y,id;}b[maxn]; 62 ll hp; 63 bool flag; 64 inline bool cmp1(rec a,rec b) 65 { 66     return a.x<b.x; 67 } 68 inline bool cmp2(rec a,rec b) 69 { 70     return a.y>b.y; 71 } 72  73 int main() 74  75 { 76  77     freopen("input.txt","r",stdin); 78  79     freopen("output.txt","w",stdout); 80  81     n=read();hp=read(); 82     l=0;r=n+1; 83     for1(i,n) 84      { 85         int x=read(),y=read(); 86          if(x<y)b[++l].x=x,b[l].y=y,b[l].id=i; 87         else b[--r].x=x,b[r].y=y,b[r].id=i; 88     } 89     sort(b+1,b+l+1,cmp1);sort(b+r,b+n+1,cmp2); 90     for1(i,n) 91     { 92         hp-=(ll)b[i].x; 93         if(hp<=0){flag=1;break;} 94         hp+=(ll)b[i].y; 95     } 96     if(flag)printf("NIE\n"); 97     else  98     { 99         printf("TAK\n");100         for1(i,n-1)printf("%d ",b[i].id);101         printf("%d\n",b[n].id);102     }103 104     return 0;105 106 }
View Code

 

BZOJ3709: [PA2014]Bohater


联系
我们