bzoj 3709 Bohater

Posted on | Views:

贪心.

首先可以对于 $d\le a$ 的怪物,按照 $d$ 从小到大的顺序,能打的都打掉.

对于剩下的怪,如果能打完,那么最后剩下的血量是确定的,与顺序无关.

倒着看,相当于是撤销掉血药的恢复,再撤销掉受到怪物的伤害,即先 $-a$ ,再 $+d$ .

那么把剩下的怪按照 $a$ 从大到小排序,能打的都打掉就可以了,前后两个阶段其实是对称的.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
//%std
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=1e5+10;
int n,p=0,q=0;
ll cur;
struct Monster
{
	int a,d,id;
	bool type;
	bool operator < (const Monster &rhs) const
	{
		return type?d<rhs.d:a>rhs.a;
	}
}x[MAXN],y[MAXN];
int ans[MAXN];
bool check()
{
	sort(x+1,x+1+p);
	sort(y+1,y+1+q);
	for(int i=1;i<=p;++i)
		if(cur<=x[i].d)
			return false;
		else
			cur+=x[i].a-x[i].d,ans[i]=x[i].id;
	for(int i=1;i<=q;++i)
		if(cur<=y[i].d)
			return false;
		else
			cur+=y[i].a-y[i].d,ans[i+p]=y[i].id;
	return true;
}
int main()
{
	n=read(),cur=read();
	for(int i=1;i<=n;++i)
	{
		Monster tmp;
		tmp.d=read(),tmp.a=read(),tmp.id=i;
		if(tmp.d<=tmp.a)
			tmp.type=true,x[++p]=tmp;
		else
			tmp.type=false,y[++q]=tmp;
	}
	bool f=check();
	puts(f?"TAK":"NIE");
	if(f)
		for(int i=1;i<=n;++i)
			printf("%d ",ans[i]);
	puts("");
	return 0;
}