[PA2014]Bohater

题目大意：

有\(n(n\le10^5)\)只怪物，你的血量为\(z\)。要打败第\(i\)只怪物时，你需要先消耗\(d_i\)点生命值，再恢复\(a_i\)点生命值。求一种打怪顺序，使得任意时刻\(x\ge0\)。

思路：

先打能加血的怪，将\(d_i\)从小到大排序后贪心；后打会扣血的怪，将\(a_i\)从大到小排序后贪心。

源代码：

#include<set>

#include<cstdio>

#include<cctype>

inline int getint() {

	register char ch;

	while(!isdigit(ch=getchar()));

	register int x=ch^'0';

	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

	return x;

}

typedef long long int64;

const int N=1e5+1;

std::set<std::pair<int,int> > set;

int d[N],a[N],ans[N];

int main() {

	const int n=getint();

	int64 z=getint();

	for(register int i=1;i<=n;i++) {

		d[i]=getint();

		a[i]=getint();

		if(d[i]<a[i]) {

			set.insert(std::make_pair(d[i],i));

		}

	}

	while(!set.empty()) {

		if(z<=set.begin()->first) {

			puts("NIE");

			return 0;

		}

		const int id=set.begin()->second;

		z+=a[id]-d[id];

		ans[++ans[0]]=id;

		set.erase(set.begin());

	}

	for(register int i=1;i<=n;i++) {

		if(d[i]>=a[i]) {

			set.insert(std::make_pair(a[i],i));

		}

	}

	while(!set.empty()) {

		if(z<=d[set.rbegin()->second]) {

			puts("NIE");

			return 0;

		}

		const int id=set.rbegin()->second;

		z+=a[id]-d[id];

		ans[++ans[0]]=id;

		set.erase(--set.end());

	}

	puts("TAK");

	for(register int i=1;i<=n;i++) {

		printf("%d%c",ans[i]," \n"[i==n]);

	}

	return 0;

}