bzoj-3709 PA-2014 Bohater

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

数据范围：$1\le n,Hp_{ori}\le 10^5$，$0\le d_i,a_i\le 10^5$。

想法：

期望找到这样一个顺序是的打完不死掉。

我们把怪物分成两种。

第一种是打完了之后加血的，第二种是打完了之后扣血的。

第一种的话，我们按照攻击力从低到高排序这个很好理解。

第二种我们按照回写的高低排序这样的话反正左右都是打，显然最后回血越多的越优先。

最后，毋庸置疑的是先打第一种后打第二种。

代码：

#include <bits/stdc++.h>

#define N 100010

using namespace std;

typedef long long ll;

char *p1,*p2,buf[100000];

#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)

int rd() {int x=0,f=1; char c=nc(); while(c<48) {if(c=='-') f=-1; c=nc();} while(c>47) x=(((x<<2)+x)<<1)+(c^48),c=nc(); return x*f;}

struct Node {ll atk,hp; int id;}a[N];

inline bool cmp(const Node &a,const Node &b)

{

	int x=a.hp-a.atk,y=b.hp-b.atk;

	if(x>=0 && y>=0) return a.atk < b.atk;

	else if(x*y <= 0) return x >= 0;

	else return a.hp>b.hp;

}

int main()

{

	ll n=rd(),m=rd();

	for(int i=1;i<=n;i++) a[i].atk=rd(),a[i].hp=rd(),a[i].id=i;

	sort(a+1,a+n+1,cmp);

	for(int i=1;i<=n;i++)

	{

		m-=a[i].atk;

		if(m<=0) puts("NIE"),exit(0);

		m += a[i].hp;

	}

	puts("TAK");

	for(int i=1;i<=n;i++) printf("%d ",a[i].id);

	puts("");

	return 0;

}

小结：这种贪心题一定要多积累。

巴特西

[bzoj3709][PA2014]Bohater_贪心

bzoj-3709 PA-2014 Bohater

最新文章

热门文章