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
一道贪心…… 贪心思想：首先按照d升序打能加血的怪，然后按a降序打减血的怪 然而没有看清数据范围，没打longlong调了好长时间……md你个智障！
#include <iostream> #include <cstdio> #include <algorithm> using namespace std; typedef long long LL; struct Monster { int a, d, id; }m[100010], m1[100010], m2[100010]; bool cmp_1(Monster a, Monster b) { return a.d < b.d; } bool cmp_2(Monster a, Monster b) { return a.a > b.a; } int main() { int n; LL z; scanf("%d%lld", &n, &z); int cnt1 = 0, cnt2 = 0; for(int i = 1; i <= n; i++) { scanf("%d%d", &m[i].d, &m[i].a); m[i].id = i; if(m[i].a >= m[i].d) m1[++cnt1] = m[i]; else m2[++cnt2] = m[i]; } sort(m1 + 1, m1 + 1 + cnt1, cmp_1); for(int i = 1; i <= cnt1; i++) { if(z <= m1[i].d) { puts("NIE"); return 0; } else z = z + m1[i].a - m1[i].d; } sort(m2 + 1, m2 + 1 + cnt2, cmp_2); for(int i = 1; i <= cnt2; i++) { if(z <= m2[i].d) { puts("NIE"); return 0; } else z = z + m2[i].a - m2[i].d; } puts("TAK"); for(int i = 1; i <= cnt1; i++) printf("%d ", m1[i].id); for(int i = 1; i <= cnt2; i++) printf("%d ", m2[i].id); return 0; }转载于:https://www.cnblogs.com/Loi-Vampire/p/6017030.html
相关资源：JAVA上百实例源码以及开源项目