POJ 3465 Battle 题解：可“反悔”的贪心

This blog post is only available in Simplified Chinse.

很多题目的贪心想法都是一个简单粗暴的贪心加上可“反悔”的操作。这样可以确保答案的正确性。

Description

You're Zhu Rengong, a formidable hero. After a number of challenging missions, you are finally facing the final Boss – a black dragon called Heilong. Due to his overwhelming power, you have to plan your actions carefully.

You have $H_1$ hit points (HP) at the beginning of the battle, and Heilong has $H_2$ . Heilong attacks you each time you do an action, and deal $A_i$ points of damage in the $i$ -th round. You have three kinds of actions.

Attack. You attack Heilong, and do x points of damage.
Defend. You focus on avoiding the attack of Heilong. This action nullifies Heilong's attack in this round.
Heal. You heal yourself, adding y hit points to yourself. There is no upper bound on your HP.

If anyone's HP drop below or equal to 0, he dies. If you can't kill the dragon within N rounds, you will also die. So you need to know how many rounds you need to kill the black dragon. If you cannot kill him, you will have to calculate the maximal damage you can do on Heilong.

Link：POJ 3465 Battle

Input

The first line contains five integers, $N, x, y, H_1, H_2. 1 \leqslant N \leqslant 10^5, 1 \leqslant x,y \leqslant 10^4, 1 \leqslant H_1,H_2 \leqslant 10^9$ . Then follow $N$ lines, the $i$ -th line contains one integer $A_{i-1}$ . $1 \leqslant A_{i-1} \leqslant 10^4$ .

Output

If you can kill Heilong, the first line of your output should be "Win". Otherwise "Lose". The second line contains the number of rounds you need to kill Heilong if the first line is "Win", or the maximal damage you can do if the first line is "Lose".

Sample Input

Sample Input 1

Sample Input 2

4 1 1000 1 4
1
10
1
1

Sample Output

Sample Output 1

Win
4

Sample Output 2

Lose
3

Hint

In Sample 1, you have to defend in the 2nd round, othewise you will die. In Sample 2, you heal yourself in the first round, and keep attacking until N rounds expires.

Translation

你是主人公（Zhu Rengong？？？），你要和一条名叫黑龙的黑龙战斗（？？？），每轮你先施展操作，然后轮到它。你有三种操作：

**攻击：**让黑龙血量减去 $x$ ；
**防御：**抵御这一轮黑龙的攻击；
**回血：**回复 $y$ 点生命值。

而黑龙每一轮的操作只会攻击你。第 $i$ 轮会对你造成 $A_i$ 的伤害。

你的初始血量是 $H_1$ ，黑龙是 $H_2$ ，谁的血量小于等于 0 了就挂了。如果你不能在 $n$ 轮之内打败它，你也会自动死亡。问你：如果你可以打败它，最少几轮可以打败；如果不能，最多对黑龙造成多少伤害。

Analysis

不得不说吴老师精选的题目不仅难度适中而且还比较有意思，~~简直比 XY 题不知道高到哪里去了~~（逃……

首先这种题目可能想到是动态规划，但是发现这个定义完全无从下手……

所以我们可以考虑一下贪心。观察题目，可以发现防御和治疗是一样的，防御就是治疗 $A_i$ 的血量，而治疗就是治疗 $y$ 的血量（这一点为之后模拟提供了方便）。

首先，我们尝试不防御、不回血，只攻击，如果直接能把黑龙打死，就直接输出答案了。如果 $n$ 轮之内没有人死，你肯定输了。接下来考虑：但是如果不能把黑龙打死，如何处理呢？我们自然想到：前面不该全部都用来攻击啊！应该抵御一下黑龙的攻击，才能让自己剩余血量更多，活得更久，伤害黑龙更多，杀死黑龙机会更大，那么显然我们想要在前面挑一轮，把这轮对黑龙的攻击改为防御（或者治疗，以下统称“抵御”），这样才可以使得自己“活得更久”。那么要让自己“活得更久”，自然要让自己剩余 HP 越大越好，所以这次抵御的攻击 $A_i$ 也要尽量大。所以我们可以用一个优先队列维护：

把每次玩家攻击、黑龙也攻击的轮（默认情况）都放到优先队列里，一旦在 $n$ 轮之内死了，就找到之前黑龙对玩家造成伤害最大的一轮，把那一轮的攻击改为抵御。这样可以保证剩余的 HP 最大，确保了解最优。其实这就相当于贪心加上了反悔的操作，是一种常用的贪心思想。

时间复杂度 $\Theta (N\log_2 N)$ 。

Code

沉迷快读，无法自拔

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>

using namespace std;
const int maxn=100005;
int n,x,y,h1,h2,ans=0,a[maxn];
struct Element{
	int x,id;
	bool operator <(Element b)const{
		return x<b.x;
	}
};
priority_queue <Element> heap;

inline int read(){
	int ret=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
	return ret*f;
}

int main(){
	n=read();x=read();y=read();h1=read();h2=read();
	for (int i=1;i<=n;i++) a[i]=read();
	int now1=h1,now2=h2,lst=0;
	for (int i=1;i<=n;i++){
		now2-=x;
		if (now2<=0){
			printf("Win\n%d\n",i);
			return 0;
		}
		now1-=a[i];heap.push((Element){a[i],i});
		if (now1<=0){
			ans=h2-now2;lst=i;
			break;
		}
	}
	if (now1>0) {printf("Lose\n%d\n",ans);return 0;}
	while (!heap.empty()){
		Element now=heap.top();heap.pop();
		now1+=max(y,now.x);
		now2+=x;
		for (int i=lst+1;i<=n;i++){
			now2-=x;
			if (now2<=0){
				printf("Win\n%d\n",i);
				return 0;
			}
			now1-=a[i];heap.push((Element){a[i],i});
			if (now1<=0){
				ans=max(ans,h2-now2);lst=i;
				break;
			}
			if (i==n) ans=max(ans,h2-now2),lst=n;
		}
		if (lst>=n) break;
	}
	printf("Lose\n%d\n",ans);
	return 0;
}

9/13/2018