BZOJ-3709-[PA2014]Bohater（贪心）

2023-08-22 21:20:52

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

题解

这道题是贪心

这里我们考虑两种情况

第一种是d[i]<a[i]的，就是打完能够回血的，显然我们需要按d[i]升序

第二种是d[i]>a[i]，即打怪只会扣血，我们倒着推，假设打完这些怪兽后剩余血量为x，那么倒着推到前面的血量就是x+d[i]-a[i]，这样的情况和情况一是差不多的，又因为是倒着推的，所以我们要按a[i]降序

 #include<bits/stdc++.h>

 #define N 100005

 #define ll long long

 using namespace std;

 int n,x,y,cnt,num;

 ll z;

 struct node{

     int fee,rec,id;

 }a[N],b[N];

 bool cmp(node x,node y){ return x.fee<y.fee; }

 bool cmp1(node x,node y){ return x.rec>y.rec; }

 int main(){

     scanf("%d%lld",&n,&z);

     for (int i=;i<=n;i++){

         scanf("%d%d",&x,&y);

         if (x<=y) a[++cnt].fee=x,a[cnt].rec=y,a[cnt].id=i;

             else b[++num].fee=x,b[num].rec=y,b[num].id=i;

     }

     sort(a+,a++cnt,cmp);

     for (int i=;i<=cnt;i++)

         if (z>a[i].fee) z+=a[i].rec-a[i].fee;

         else{ puts("NIE"); return ; }

     sort(b+,b++num,cmp1);

     for (int i=;i<=num;i++)

         if (z>b[i].fee) z+=b[i].rec-b[i].fee;

         else{ puts("NIE"); return ; }

     puts("TAK");

     for (int i=;i<=cnt;i++)

         printf("%d ",a[i].id);

     for (int i=;i<=num-;i++)

         printf("%d ",b[i].id);

     printf("%d\n",b[num].id);

     return ;

 }