题解：B4207 [常州市赛 2021] 战士
前言
题目传送门
思路讲解
思路其实很好想，因为怪物的攻击是固定的，所以战士的死亡时间也是固定的，我们就需要通过计算战士每次死亡前能造成的最大伤害
- 如果可以击败怪物，那就直接击败
- 如果击败不了，那就攻击使怪物扣血
而且，我们如果要磨刀，肯定是先磨刀再攻击
那么怎么计算最大伤害呢？
我们可以枚举磨刀次数 \(k\)，看一下伤害是多少（即攻击次数乘伤害），把这个伤害与最高伤害打擂台，最终就能得到最高伤害
Code
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;
int ih, ia, h, da, m, c[N], L = 1, R = 1;
//ih, ia, h, da, m, c意思见题目
//L, R表示当前段的起始/结束回合
signed main() {cin >> ih >> ia >> h >> da >> m;for (int i = 1; i <= m; i++)cin >> c[i];//输入数据while (R <= m) { //打怪int cur_hp = ih; //当前血量while (cur_hp > 0 && R <= m)cur_hp -= c[R++]; //挨揍int seg_len = R - L; //当前段长度int max_dmg = 0, min_kill = 1e9; //最大伤害，最小回合数for (int k = 0; k <= seg_len; k++) { //磨k次刀int atk = ia + k * da; //攻击力if (atk * (seg_len - k) >= h) { //如果能击败min_kill = min(min_kill, k + (h + atk - 1) / atk); //更新最小回合数}max_dmg = max(max_dmg, atk * (seg_len - k)); //更新最大伤害}if (min_kill != 1e9) { //如果能击败cout << L + min_kill - 1 << "\n"; //输出击败的回合return 0;}h -= max_dmg; //怪物L = R; //更新当前段起始回合}cout << -1 << "\n"; //Game Over!return 0;
}