题解【洛谷P4025】[PA2014]Bohater

题面

一开始想了很多种贪心的方式，比如按 (d_i) 升序、(a_i) 降序、(a_i-d_i) 降序，结果都被自己 hack 掉了。

于是我们考虑换一种思考方式：按照 (d_i) 与 (a_i) 的大小关系来分 (2) 种情况贪心。

• 若 (a_igeq d_i)，那么就说明打败这些怪物生命值就会增加，按照 (d_i) 升序来打这些怪物就一定是最优的；
• 若 (a_i < d_i)，说明打败这些怪物生命值会降低，此时我们按照 (a_i) 降序来打是最理想的，因为我们肯定是先打回血最多的怪物方案最优。

这道题就做完了。

#include <bits/stdc++.h>
#define DEBUG fprintf(stderr, "Passing [%s] line %d
", __FUNCTION__, __LINE__)
#define File(x) freopen(x".in","r",stdin); freopen(x".out","w",stdout)

using namespace std;

typedef long long LL;
typedef pair <int, int> PII;
typedef pair <int, PII> PIII;

inline int gi()
{
	int f = 1, x = 0; char c = getchar();
	while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return f * x;
}

inline LL gl()
{
	LL f = 1, x = 0; char c = getchar();
	while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return f * x;
}

const int INF = 0x3f3f3f3f, N = 1000003;

LL n, m, tot1, tot2;
LL z;
struct Monster
{
	LL d, a, id;
} x[N], y[N];
vector <LL> ansid;

inline bool cmp(Monster x, Monster y)
{
	return x.a > y.a;
}

inline bool cmp1(Monster x, Monster y)
{
	return x.d < y.d;
}

int main()
{
	//File("");
	n = gl(), z = gl();
	for (int i = 1; i <= n; i+=1)
	{
		LL d = gl(), a = gi();
		if (d <= a) x[++tot1] = (Monster){d, a, i};
		else y[++tot2] = (Monster){d, a, i};
	}
	sort(x + 1, x + 1 + tot1, cmp1);
	sort(y + 1, y + 1 + tot2, cmp);
	for (int i = 1; i <= tot1; i+=1)
		if (z <= x[i].d) {puts("NIE"); return 0;}
		else z += x[i].a - x[i].d, ansid.push_back(x[i].id);
	for (int i = 1; i <= tot2; i+=1)
		if (z <= y[i].d) {puts("NIE"); return 0;}
		else z += y[i].a - y[i].d, ansid.push_back(y[i].id);
	puts("TAK");
	for (auto oo : ansid) printf("%lld ", oo);
	return 0;
}