题解 P4025 【[PA2014]Bohater】
lgswdn_SA
·
·
题解
LG4025 Bohater
传送门：https://www.luogu.com.cn/problem/P4025
题意
一开始有 z 点血。有 n 只怪物，每只怪物需要先消耗 d_i 点血，然后会恢复 a_i 点血。中途不能死掉。求一种可行的打怪顺序。
一个需要思考的贪心。
## 题解
首先一个很明显的贪心，先打打了可以回血的怪物，再打打了会掉血的怪物。
这个贪心的一个证明：假如一个回血怪物放在掉血怪物前面都没法打掉，那么放在掉血怪物后面更不可能打掉。
然后考虑回血怪物以及掉血怪物内部的安排贪心。
先考虑回血怪物。
1. 对于那些 $d_i<z$ 的回血怪物，直接打即可。
2. 对于不能的，按照 $d_i$ 从小到大排序。可以用调整法证明。
然后考虑掉血怪物。有两种理解方法。第一种还是用调整法来做。第二种我们可以发现，如果倒过来反向看，掉血怪物相当于回血怪物（从终局往回走，$a_i$ 作为掉血量，$d_i$ 作为回血量，每次血量都不能小于 $0$），于是我们按照倒叙视角的“掉血量”排序，即按照 $a_i$ 排序。
排完序模拟即可。
```cpp
#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;
}
```