终局

终局

题目描述

云天河一行人终于在踏上卷云台，最终决战拉开帷幕，这个战斗的过程可以看成由 n 个回合组成，对于每一个回合，云天河先行动，玄霄再行动。战斗一开始时，云天河有 A 点血，玄霄有 B 点血。
每回合开始时，云天河可以有 3 个选择：
恸天贯日式:云天河以凝冰诀之气灌于剑身，借助神器后羿射日弓，剑出有贯日之势，对玄霄造成 X 点伤害。
格挡:云天河该回合能处于绝对防御状态，这回合中玄霄无法对云天河造成伤害。
雨润:云天河能瞬间恢复 Y 点血
而玄霄每一回合都只会向云天河使用 燃冰焚炎 ，第 i 回合造成的伤害为 ci。一旦云天河或是玄霄的血量小于或等于 0 了，他就会立即死亡。可以看出，云天河与玄霄对战的策略是非常重要的，所以你需要帮云天河设计一个最优的方案：如果云天河能在 n 回合内战胜玄霄，你就要找出最少的回合；而如果无论如何云天河都不能在 n 回合内战胜玄霄，你就需要算出云天河能对玄霄造成的最大伤害值。

输入

第一行为 5 个数，分别为 n，X，Y，A，B，意义见描述
接下来 n 行，每行 1 个数 ci，意义见描述
n<=1e5,A,B<=1e9,ci,X,Y<=1e4

输出

包括两行。
如果能战胜玄霄，则第一行输出“Win”，第二行输出战胜玄霄花费的最少的回合
数。
如果无论如何都不能在 n 回合内战胜，则在第一行输出“Lose”，第二行输出能
云天河对玄霄造成的最大伤害值。

样例输入

4 1 1 3 3

1

10

1

10

样例输出

Win

4

思路

因为回血和防守可以直接考虑一下，抗了伤害还能回血就回血，否则就防御

默认攻击对手，如果会被打死，有两个选择

1.以前的某一次不打，这次打，2.这次不打

优先队列维护反悔后能回的血量最大值

AC代码

#include <iostream>
#include <stdio.h>
#include <queue>
#include <set>
#include <string>
#include <map>
#include <cmath>
#include <algorithm>
#include <cstring>
#define ll long long
using namespace std;
const int maxn = 1e5 + 5;
const int inf = 0x3f3f3f3f;
int c[maxn];
priority_queue<int> pq;
int main()
{int n, x, y, A, B;while (~scanf("%d %d %d %d %d", &n, &x, &y, &A, &B)){while (!pq.empty())pq.pop();for (int i = 1; i <= n; ++i)scanf("%d", &c[i]);int tim = B / x;if (B % x)++tim;int ju = 0, k = 0, ans = 0;for (int i = 1; i <= n; ++i){++k;ans=max(ans,k);if (k == tim){ju = i;break;}pq.push(max(y, c[i]));if (A > c[i]){A -= c[i];continue;}--k;A += pq.top();A -= c[i];pq.pop();}if (ju)printf("Winn%dn", ju);elseprintf("Losen%dn", ans * x);}return 0;
}