bzoj 3709: [PA2014]Bohater 贪心

题目:

在一款电脑游戏中，你需要打败\(n\)只怪物（从\(1\)到\(n\)编号）。为了打败第\(i\)只怪物，你需要消耗\(d_i\)点生命值，但怪物死后会掉落血药，使你恢复\(a_i\)点生命值。任何时候你的生命值都不能降到\(0\)（或\(0\)以下）。请问是否存在一种打怪顺序，使得你可以打完这\(n\)只怪物而不死掉

所有数均\(\leq 10^5\)

题解:

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

顺序的话稍微\(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;

}

巴特西

bzoj 3709: [PA2014]Bohater 贪心

题目:

题解:

最新文章

热门文章