题目:

题解:

首先很明显地要先收掉所有总收益为正的怪物。

顺序的话稍微\(YY\)一下就会发现是按照消耗的生命值从小到大。

那么下面考虑如何收剩下的总收益为负的怪物。

容易发现,如果我们从前往后收怪\(HP\)没有\(\leq 0\)过。

那么这个过程的逆过程也满足这个条件。

所以考虑如果提前取得所有的收益,然后倒着做这个过程。

这样就变成了收掉总收益为正的怪物的部分。

所以按照回复的\(HP\)从小到大收即为逆过程的最有策略。

(由于是逆过程,所以之前的回复即为逆过程的消耗)

所以按照回复的\(HP\)从大到小排序收取即为原过程的最有解。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(ll &x){
x=0;char ch;bool flag = false;
while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
#define rg register int
#define rep(i,a,b) for(rg i=(a);i<=(b);++i)
#define per(i,a,b) for(rg i=(a);i>=(b);--i)
const ll maxn = 100010;
struct Node{
ll nd,val,id;
bool vis;
Node(){vis = false;}
Node(const ll &a,const ll &b){
nd = a;val = b;vis = false;
}
}a[maxn];
inline bool cmp1(const Node &a,const Node &b){
return a.nd == b.nd ? a.val > b.val : a.nd < b.nd;
}
inline bool cmp2(const Node &a,const Node &b){
return a.val+a.nd > b.val+b.nd;
}
bool vis[maxn];
ll ans[maxn],cnt;
int main(){
ll n,h;read(n);read(h);
ll x,y;
rep(i,1,n){
read(x);read(y);
a[i] = Node(x,y-x);
a[i].id = i;
}sort(a+1,a+n+1,cmp1);
rep(i,1,n){
if(h > a[i].nd && a[i].val >= 0){
h += a[i].val;
ans[++cnt] = a[i].id;
a[i].vis = true;
}
}
rep(i,1,n) if(a[i].vis == false && h <= a[i].nd){
puts("NIE");return 0;
}
sort(a+1,a+n+1,cmp2);
rep(i,1,n) if(a[i].vis == false){
if(h > a[i].nd){
h += a[i].val;
ans[++ cnt] = a[i].id;
a[i].vis = true;
}else{
puts("NIE");
return 0;
}
}
puts("TAK");
rep(i,1,cnt){
printf("%lld",ans[i]);
if(i != cnt) putchar(' ');
else putchar('\n');
}
return 0;
}
05-11 09:32
查看更多