[文章目录]
Description
在一款电脑游戏中，你需要打败n只怪物（从1到n编号）。为了打败第i只怪物，你需要消耗d[i]点生命值，但怪物死后会掉落血药，使你恢复a[i]点生命值。任何时候你的生命值都不能降到0（或0以下）。请问是否存在一种打怪顺序，使得你可以打完这n只怪物而不死掉1<=n,z<=100000,0<=d[i],a[i]<=100000
贪心。
考虑a>b的怪物，策略一定是先打，并且按门槛的递增顺序，显然是最优的。
对于a<b的怪物，考虑如果两个交换使得不能够完成任务的充要条件：
设血量为z，那么说明：
z>d1且z-d1+a1>d2且z>d2且z-d2+a2d2+d1-z,a2<d1+d2-z那么当且仅当a1>a2的时候成立，所以按照a的递减排序直接搞。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
long long z;
struct node
{
int d,a,id;
}a[100010];
bool cmp1(node x,node y) {return x.d<y.d;}
bool cmp2(node x,node y) {return x.a>y.a;}
int main()
{
scanf("%d%d",&n,&z);
int x,y,tot=0,tot2=n;
for(int i=1;i<=n;++i)
{
scanf("%d%d",&x,&y);
if(x<y) a[++tot]=(node){x,y,i};
else a[tot2--]=(node){x,y,i};
}
sort(a+1,a+tot+1,cmp1);
sort(a+tot+1,a+n+1,cmp2);
for(int i=1;i<=n;++i)
{
if(z<=a[i].d) {puts("NIE"); return 0;}
z=z-a[i].d+a[i].a;
}
puts("TAK");
for(int i=1;i<=n;++i)
printf("%d%c",a[i].id,(i==n)?'\n':' ');
return 0;
}