首页 > 代码库 > BZOJ 3709: [PA2014]Bohater

BZOJ 3709: [PA2014]Bohater

2024-07-30 20:07:12   213人阅读

题目

3709: [PA2014]Bohater

Time Limit: 5 Sec  Memory Limit: 128 MBSec  Special Judge
Submit: 507  Solved: 163
[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

题解

这道题目很明显是贪心，一开始直接去能回血的，而且很明显是从损失体力晓得开始回，这样可以保证在有解情况下能得到全部恢复。而，接下来的打怪阶段，我们可以看作一个回血的逆过程，把打怪过程倒过来看就和之前的回血一样了，所以是倒过来的贪心规则，则血药降序。然后模拟看看能不能打完就好！

代码

 1 /*Author:WNJXYK*/ 2 #include<cstdio> 3 #include<iostream> 4 #include<string> 5 #include<algorithm> 6 using namespace std; 7  8 const int Maxn=100000; 9 struct Node{10     long long r,d;11     int index;12 };13 Node rec[Maxn+10],dam[Maxn+10];14 int recs,dams;15 long long n,z;16 17 bool cmp1(Node a,Node b){18     if (a.d<b.d) return true;19     if (a.d==b.d && a.r>b.r) return true;20     return false;21 }22 23 bool cmp2(Node a,Node b){24     if (a.r>b.r) return true;25     if (a.r==b.r && a.d<b.d) return true;26     return false; 27 }28 29 int main(){30     scanf("%lld%lld",&n,&z);31     for (int i=1;i<=n;i++){32         long long reco,dama;33         scanf("%lld%lld",&dama,&reco);34         if (reco>=dama){35             rec[++recs].r=reco;36             rec[recs].d=dama;37             rec[recs].index=i;38         }else{39             dam[++dams].r=reco;40             dam[dams].d=dama;41             dam[dams].index=i;42         }43     }44     sort(rec+1,rec+1+recs,cmp1);45     sort(dam+1,dam+1+dams,cmp2);46     for (int i=1;i<=recs;i++){47         if (z>rec[i].d){48             z+=rec[i].r-rec[i].d;49         }else{50             printf("NIE\n");51             return 0;52         }53     }54     for (int i=1;i<=dams;i++){55         if (z>dam[i].d){56             z+=dam[i].r-dam[i].d;57         }else{58             printf("NIE\n");59             return 0;60         }61     }62     printf("TAK\n");63     for (int i=1;i<=recs;i++) printf("%d ",rec[i].index);64     for (int i=1;i<=dams;i++) printf("%d ",dam[i].index); 65     return 0;66 }
View Code

 

BZOJ 3709: [PA2014]Bohater


联系
我们