描述 Description
在一款电脑游戏中，你需要打败 n 只怪物（从 1 到 n 编号）。为了打败第 i 只怪物，你需要消耗 d[i] 点生命值，但怪物死后会掉落血药，使你恢复 a[i] 点生命值。任何时候你的生命值都不能降到 0（或 0 以下）。请问是否存在一种打怪顺序，使得你可以打完这 n 只怪物而不死掉。
输入格式 InputFormat
第一行两个整数 n,z(1<=n,z<=100000)，分别表示怪物的数量和你的初始生命值。
接下来 n 行，每行两个整数 d[i],ai
输出格式 OutputFormat
第一行为 TAK（是）或 NIE（否），表示是否存在这样的顺序。
如果第一行为 TAK，则第二行为空格隔开的 1~n 的排列，表示合法的顺序。如果答案有很多，你可以输出其中任意一个。
样例输入 SampleInput
3 5
3 1
4 8
8 3
样例输出 SampleOutput
TAK
2 3 1
代码 Code
先打不会让自己掉血的怪，比如按照 d 值升序打；接着打剩下的怪，因为如果能够都打完的话会发现其实是将 a 和 d 值反过来看，即按照 a 的降序打怪。
好像没有 special judge…
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int i,j,t,n,m,l,r,k;
struct monster
{
int d,a,id;
}ma[100005],mb[100005];
int sa,sb;
long long z,y,x;
inline bool compa(monster a,monster b)
{
return a.d<b.d;
}
inline bool compb(monster a,monster b)
{
return a.a>b.a;
}
inline bool kill(monster* s,int ss)
{
int i,j,t;
for (i=1;i<=ss;i++)
{
if (z<=s[i].d)
{
printf("NIE\n");
return false;
}
z+=s[i].a-s[i].d;
}
return true;
}
int main()
{
sa=sb=0;
scanf("%d%lld",&n,&z);
for (i=1;i<=n;i++)
{
scanf("%lld%lld",&x,&y);
if (x<=y)
{
ma[++sa].d=x;ma[sa].a=y;ma[sa].id=i;
}
else
{
mb[++sb].d=x;mb[sb].a=y;mb[sb].id=i;
}
}
sort(ma+1,ma+sa+1,compa);
sort(mb+1,mb+sb+1,compb);
if (!kill(ma,sa)) return 0;
if (!kill(mb,sb)) return 0;
printf("TAK\n");
for (i=1;i<=sa;i++) printf("%d",ma[i].id);
for (i=1;i<=sb;i++) printf("%d",mb[i].id);
return 0;
}