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

Sample Output

TAK
2 3 1

---

題解Here!

這就是個貪心。。。

首先，先把殺掉能回血的先殺了，這是肯定的。

顯然殺的順序按照消耗升序。

殺完以后，不管用什么順序殺掉剩下的怪，最后體力的剩余值是確定的。

倒序來看，相當于將血藥吐出來然后返還殺怪的消耗，那么顯然也是按照損失體力（即血藥回血量）升序，正回來即是降序。。。

即分為兩部分，殺完能回血的按照消耗升序，剩余按血藥回血量降序，然后模擬一遍判斷是否合法即可。

注：記得血量要開$long\ long$，活坑。。。

附代碼：

#include<iostream> #include<algorithm> #include<cstdio> #define MAXN 100010 using namespace std; int n; long long m; int top1=0,top2=0; struct node{long long x,y;int id; }a[MAXN],b[MAXN]; inline int read(){int date=0,w=1;char c=0;while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}return date*w; } inline bool cmp1(const node &p,const node &q){return p.x<q.x; } inline bool cmp2(const node &p,const node &q){return p.y>q.y; } void work(){for(int i=1;i<=top1;i++){if(m<=a[i].x){printf("NIE\n");return;}else m-=a[i].x-a[i].y;}for(int i=1;i<=top2;i++){if(m<=b[i].x){printf("NIE\n");return;}else m-=b[i].x-b[i].y;}printf("TAK\n");for(int i=1;i<=top1;i++)printf("%d ",a[i].id);for(int i=1;i<=top2;i++)printf("%d ",b[i].id);printf("\n"); } void init(){n=read();m=read();for(int i=1;i<=n;i++){int x=read(),y=read();if(x<=y){top1++;a[top1].x=x;a[top1].y=y;a[top1].id=i;}else{top2++;b[top2].x=x;b[top2].y=y;b[top2].id=i;}}sort(a+1,a+top1+1,cmp1);sort(b+1,b+top2+1,cmp2); } int main(){init();work();return 0; }

?

轉載于:https://www.cnblogs.com/Yangrui-Blog/p/9507374.html

總結

以上是生活随笔為你收集整理的BZOJ3709: [PA2014]Bohater的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。