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
3 1
4 8
8 3
Sample Output
TAK
2 3 1
2 3 1
题解
首先题目看完很容易想到就是贪心，显然的是要先打回血的，再打扣血的。
那么我们将这些怪分成两部分，第一部分回血的：容易得到到的是，因为回回血，所以我们要先打代价低的即$d_i$越小越先打。
那么我们接着考虑第二部分，当时猜了两个策略：第一是还是按$d_i$递增，但显然样例都满足不了这种策略，舍去。
第二种就是按照$a_i$递减来打，原因是使得自己前期扣血少。提交了发现$A$了，但后一部分的策略显然是个笼统的解释。
搜到了hzwer的题解，大致就是后面一部分是前一部分的逆过程。
//It is made by Awson on 2017.10.15
#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define Min(a, b) ((a) < (b) ? (a) : (b))
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define sqr(x) ((x)*(x))
using namespace std;
const int N = ; int n;
LL z;
struct tt {
int d, a, id;
}a[N+];
bool comp1(const tt &a, const tt &b) {
return a.d-a.a < b.d-b.a;
}
bool comp2(const tt &a, const tt &b) {
return a.d < b.d;
}
bool comp3(const tt &a, const tt &b) {
return a.a > b.a;
} void work() {
scanf("%d%lld", &n, &z);
for (int i = ; i <= n; i++) scanf("%d%d", &a[i].d, &a[i].a), a[i].id = i;
sort(a+, a+n+, comp1);
int lim = n;
for (int i = ; i <= n; i++) if (a[i].d > a[i].a) {
lim = i-; break;
}
if (lim >= ) sort(a+, a+lim+, comp2);
if (lim < n) sort(a++lim, a+n+, comp3);
for (int i = ; i <= n; i++) {
z -= a[i].d;
if (z <= ) {
printf("NIE\n");
return;
}
z += a[i].a;
}
printf("TAK\n");
for (int i = ; i <= n; i++) printf("%d ", a[i].id);
}
int main() {
work();
return ;
}