Description
在一款电脑游戏中，你需要打败n只怪物（从1到n编号）。为了打败第i只怪物，你需要消耗d[i]点生命值，但怪物死后会掉落血药，使你恢复a[i]点生命值。任何时候你的生命值都不能降到0（或0以下）。请问是否存在一种打怪顺序，使得你可以打完这n只怪物而不死掉
Input
第一行两个整数n,z(1<=n,z<=100000)，分别表示怪物的数量和你的初始生命值。
接下来n行，每行两个整数d[i],ai
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
思路： 竟然不需要dp！感觉对贪心的局部最优==全局最优有了更深的理解。
我们需要贪的是：使得每次一打完怪，剩余血量尽可能的大，这样打怪才不容易出现0或负数。
分为两种情况贪，第一种是伤害小于回血的。这种情况下血量是增长的，这个时候要尽量使血量能够大于伤害，优先打伤害小的才能保证打更多怪。
第二种是伤害大于回血的。因为血量是逐渐变少的，那么打任何一种怪都必须使得血量大于伤害。这个时候要使得打更多的怪，就要使得血量下降的更慢，那么我们优先打回血最多的怪。
这两种贪法就保证了全局最优。
#include <cstdio>
#include <algorithm>
#include <vector>using namespace std;
const int maxn = 1e6 + 7;
typedef long long ll;
vector<pair<pair<int,int>,int> >p1;
vector<pair<pair<int,int>,int> >p2;
vector<int>ans;int cmp1(pair<pair<int,int>,int> a,pair<pair<int,int>,int> b)
{return a.first.first < b.first.first;//先打血量小的
}int cmp2(pair<pair<int,int>,int> a,pair<pair<int,int>,int> b)
{return a.first.second > b.first.second;//先打回血多的
}int main()
{int n;ll z;scanf("%d%lld",&n,&z);for(int i = 1;i <= n;i++){int d,a;scanf("%d%d",&d,&a);pair<pair<int,int>,int>t;t.first.first = d;t.first.second = a;t.second = i;if(d <= a)p1.push_back(t);elsep2.push_back(t);}sort(p1.begin(),p1.end(),cmp1);for(int i = 0;i < p1.size();i++){if(z <= p1[i].first.first){printf("NIE\n");return 0;}else{z += p1[i].first.second;z -= p1[i].first.first;ans.push_back(p1[i].second);}}sort(p2.begin(),p2.end(),cmp2);for(int i = 0;i < p2.size();i++){if(z <= p2[i].first.first){printf("NIE\n");return 0;}else{z += p2[i].first.second;z -= p2[i].first.first;ans.push_back(p2[i].second);}}printf("TAK\n");for(int i = 0;i < ans.size();i++)printf("%d ",ans[i]);return 0;
}