https://codeforces.com/contest/903/problem/B
题目大意
一个回合制游戏，主角血量是 $h_1$ 攻击力 $a_1$ 有无限多的药，每次可以恢复 $c_1$ 的血量（恢复可以超出 $h_1$）。有怪物血量 $h_2$ 攻击力 $a_2$。每个回合：
- 主角选择攻击或恢复，攻击则 $h_2$ 减少 $a_1$ 否则 $h_1$ 增加 $c_1$。
- 怪物攻击 $h_1$ 减少 $a2$。
如果经过 1 怪物血量少于等于 $0$ 则战斗即刻结束。保证任意时刻主角血量不小于等于 $0$ 的情况下，最少要多少个回合可以使主角战胜怪物。并输出任意最优方案。
$1 \le h_1, a_1, h_2, a_2 \le 100$
$a_2 < c_1 \le 100$。
简要题解
显然最后一次操作一定是攻击。
由于有 $a_2 < c_1$ 的限制，显然总是可以战胜怪物的。因为没有血量上限，因此如果需要 $k$ 次恢复，则总是可以在开始进行恢复。因为所有攻击前的被攻击次数不变（血量减少不变），提前恢复只会使得加血变多。因为加血的轮次怪物一定没死，因此相当于这样的每个轮次可以多 $c_1 - a_2$ 点生命。
分情况讨论一下不用加血的情况即可。
复杂度
$T$：$O(1)$
$S$：$O(1)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
void solve() {
int h1, a1, c1;
int h2, a2;
cin >> h1 >> a1 >> c1 >> h2 >> a2;
h1--;
int round = (h2 + a1 - 1) / a1;
if (h1 / a2 >= round - 1) {
cout << round << '\n';
for (int i = 0; i < round; i++) {
cout << "STRIKE\n";
}
return;
}
int need = (round - 1) * a2 - h1;
int heal = (need + (c1 - a2) - 1) / (c1 - a2);
cout << (round + heal) << '\n';
for (int i = 0; i < heal; i++) {
cout << "HEAL\n";
}
for (int i = 0; i < round; i++) {
cout << "STRIKE\n";
}
}
int main() {
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: [CF] F. Clear The Matrix - Educational Codeforces Round 34 (Rated for Div. 2)