贪心...
可以回血的按d[i]升序防止死掉
不能回血的按a[i]降序，因为只考虑d我们要扣除的血量是一定的，为了不死显然回血多的放前面更好
#include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #include<algorithm> #define ll long long using namespace std; const int maxn=500010,inf=1e9; struct poi{ll t,d,pos;}a[maxn],b[maxn]; ll n,m,x,y,z,tot,cnt1,cnt2; void read(ll &k) { int f=1;k=0;char c=getchar(); while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); while(c<='9'&&c>='0')k=k*10+c-'0',c=getchar(); k*=f; } bool cmp1(poi a,poi b){return a.d<b.d;} bool cmp2(poi a,poi b){return a.t>b.t;} int main() { read(n);read(z); for(int i=1;i<=n;i++) { read(x);read(y); if(x<=y)a[++cnt1].d=x,a[cnt1].t=y,a[cnt1].pos=i; else b[++cnt2].d=x,b[cnt2].t=y,b[cnt2].pos=i; } sort(a+1,a+1+cnt1,cmp1); sort(b+1,b+1+cnt2,cmp2); for(int i=1;i<=cnt1;i++) { z-=a[i].d; if(z<=0)return puts("NIE"),0; z+=a[i].t; } for(int i=1;i<=cnt2;i++) { z-=b[i].d; if(z<=0)return puts("NIE"),0; z+=b[i].t; } puts("TAK"); for(int i=1;i<=cnt1;i++)printf("%lld ",a[i].pos); for(int i=1;i<=cnt2;i++)printf("%lld ",b[i].pos); return 0; }