BZOJ3709 Bohater 贪心

传送门

---

思路很妙……

有个前提条件：血量无限，这样话肯定先打会回血的怪，再打会掉血的怪

对于会回血的怪，按照受到伤害的顺序从小往大打

对于会掉血的怪似乎并不是很好搞，考虑：将每一时刻的血量函数画出来，然后反过来看（从右往左看这个函数），就相当于回血量和掉血量互换，会掉血的怪会变成会回血的怪。因为最终的血量是已知的，所以按照上面的方法再做一遍就可以了。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<ctime>

#include<cctype>

#include<algorithm>

#include<cstring>

#include<iomanip>

#include<queue>

#include<map>

#include<set>

#include<bitset>

#include<vector>

#include<stack>

#include<cmath>

//This code is written by Itst

using namespace std;

inline int read(){

	int a = 0;

	char c = getchar();

	bool f = 0;

	while(!isdigit(c) && c != EOF){

		if(c == '-')

			f = 1;

		c = getchar();

	}

	if(c == EOF)

		exit(0);

	while(isdigit(c)){

		a = a * 10 + c - 48;

		c = getchar();

	}

	return f ? -a : a;

}

#define PII pair < int , int >

#define st first

#define nd second

#define PIII pair < PII , int >

#define auto vector < PIII > :: iterator

vector < PIII > mons[2];

long long hp , End;

int N;

signed main(){

#ifndef ONLINE_JUDGE

	freopen("in","r",stdin);

	//freopen("out","w",stdout);

#endif

	N = read(); End = hp = read();

	for(int i = 1 ; i <= N ; ++i){

		int d = read() , a = read();

		a >= d ?

			mons[0].push_back(PIII(PII(d , a) , i)) :

			mons[1].push_back(PIII(PII(a , d) , i));

		End = End - d + a;

	}

	if(End <= 0){puts("NIE"); return 0;}

	sort(mons[0].begin() , mons[0].end());

	for(auto t = mons[0].begin() ; t != mons[0].end() ; ++t){

		if(hp - (*t).st.st <= 0){

			puts("NIE"); return 0;

		}

		hp = hp - (*t).st.st + (*t).st.nd;

	}

	sort(mons[1].begin() , mons[1].end());

	for(auto t = mons[1].begin() ; t != mons[1].end() ; ++t){

		if(End - (*t).st.st <= 0){

			puts("NIE"); return 0;

		}

		End = End - (*t).st.st + (*t).st.nd;

	}

	puts("TAK");

	for(auto t = mons[0].begin() ; t != mons[0].end() ; ++t)

		printf("%d " , (*t).nd);

	reverse(mons[1].begin() , mons[1].end());

	for(auto t = mons[1].begin() ; t != mons[1].end() ; ++t)

		printf("%d " , (*t).nd);

	return 0;

}