【贪心】BZOJ3709 [PA2014]Bohater

题面在这里

​

显然先打那些\(a>d\)的怪

这些按照\(d\)排序

对于\(d>a\)的怪，考虑打完后的血是一定的，把过程反过来，就是前面的情况了，按照\(a\)排序

​

示例程序：

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;

const int maxn=100005;
int n;ll z;
struct data{
	int d,s,id;
	bool operator<(const data&b)const{
		if ((d<s)^(b.d<b.s)) return d<s;
		if (d<s) return d<b.d;
		return s>b.s;
	}
}a[maxn];
int main(){
	scanf("%d%lld",&n,&z);
	for (int i=1;i<=n;i++) scanf("%d%d",&a[i].d,&a[i].s),a[i].id=i;
	sort(a+1,a+1+n);
	for (int i=1;i<=n;i++)
	 if (z>a[i].d) z+=-a[i].d+a[i].s;
	 else return puts("NIE"),0;
	puts("TAK");
	for (int i=1;i<=n;i++) printf("%d ",a[i].id);
	return 0;
}