自动搬运

查看原文

来自洛谷，原作者为

	lgswdn_SA 舞台少女，每日进化中

搬运于2025-08-24 21:55:41，当前版本为作者最后更新于2020-10-20 22:34:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

LG4025 Bohater

传送门：https://www.luogu.com.cn/problem/P4025

题意

一开始有 $z$ 点血。有 $n$ 只怪物，每只怪物需要先消耗 $d_i$ 点血，然后会恢复 $a_i$ 点血。中途不能死掉。求一种可行的打怪顺序。

$1\le n,z\le 10^5$。

一个需要思考的贪心。

题解

首先一个很明显的贪心，先打打了可以回血的怪物，再打打了会掉血的怪物。

这个贪心的一个证明：假如一个回血怪物放在掉血怪物前面都没法打掉，那么放在掉血怪物后面更不可能打掉。

然后考虑回血怪物以及掉血怪物内部的安排贪心。

先考虑回血怪物。

1. 对于那些 $d_i<z$ 的回血怪物，直接打即可。
2. 对于不能的，按照 $d_i$ 从小到大排序。可以用调整法证明。

然后考虑掉血怪物。有两种理解方法。第一种还是用调整法来做。第二种我们可以发现，如果倒过来反向看，掉血怪物相当于回血怪物（从终局往回走，$a_i$ 作为掉血量，$d_i$ 作为回血量，每次血量都不能小于 $0$），于是我们按照倒叙视角的“掉血量”排序，即按照 $a_i$ 排序。

排完序模拟即可。

#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
using namespace std;
const int N=1e5+9;

int n,sum,ans[N];
struct mons {int d,a,id;} a[N];
bool cmp(const mons &x, const mons &y) {
	if((x.a-x.d)*(y.a-y.d)<0) return x.a-x.d>0;
	else if(x.a-x.d<0) return x.a>y.a;
	else return x.d<y.d;
}

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

signed main() {
	n=read(), sum=read();
	rep(i,1,n) a[i].d=read(), a[i].a=read(), a[i].id=i;
	sort(a+1,a+n+1,cmp);
	rep(i,1,n) {
		sum-=a[i].d;
		if(sum<=0) return puts("NIE"), 0;
		ans[i]=a[i].id;
		sum+=a[i].a;
	}
	puts("TAK");
	rep(i,1,n) printf("%lld ",ans[i]);
	return 0;
}