bzoj 3709 [PA2014]Bohater

3709: [PA2014]Bohater
Time Limit: 5 Sec Memory Limit: 128 MBSec Special Judge
Submit: 3211 Solved: 1005
[Submit][Status][Discuss]

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

简单贪心。

我们肯定优先打能回血的，但不能直接把能回血的加上，因为不一定能大死。

所以我们能回血的按照d从小到大。

不能回血的，我们按照a从大到小。

会爆int

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int n,z;
struct node{int d,a,id;};
vector<int> res; vector<node> v1,v2;
int cmp1(node s1,node s2){return s1.d<s2.d;}
int cmp2(node s1,node s2){return s1.a>s2.a;}
signed main(){
	cin>>n>>z;
	for(int i=1,d,a;i<=n;i++){
		scanf("%lld %lld",&d,&a);
		if(a>=d)	v1.push_back({d,a,i});
		else	v2.push_back({d,a,i});
	}
	sort(v1.begin(),v1.end(),cmp1);	sort(v2.begin(),v2.end(),cmp2);
	for(int i=0,m=v1.size();i<m;i++){
		if(z>v1[i].d){z-=v1[i].d; z+=v1[i].a; res.push_back(v1[i].id);}
		else	return puts("NIE"),0;
	}
	for(int i=0,m=v2.size();i<m;i++){
		if(z>v2[i].d){z-=v2[i].d; z+=v2[i].a; res.push_back(v2[i].id);}
		else	return puts("NIE"),0;
	}
	puts("TAK");
	for(int i=0,m=res.size();i<m;i++)	printf("%lld ",res[i]);puts("");
	return 0;
}