【例42.1】 雇佣兵

解题思路

战斗力为N时，恢复M体力最少需ceil(M/N)个元素。若剩余元素够，扣除后参加一次战斗，增加floor(M/N)战斗力，再进入下一轮。N>M时一轮再无提升，可结束。

正确性说明

计算规则直接来自题目定义。按所述顺序处理时，已完成部分的结果被准确保存在累加量、计数或当前状态中；下一步只加入新增贡献。最终得到完整要求的结果。

易错点

初始体力0，首次战斗也要消耗元素；本轮提升按开始时战斗力计算。

复杂度

若完成k个战斗期，时间O(k)，空间O(1)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

每期只有满体力才能参加，ceil(M / N)
    是不可降低的元素开销且能够达到；用最少元素完成每期保留最多后续资源，因此可实现最多成长。 int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long M, N, X;
    cin >> M >> N >> X;
    while (N <= M) {
        long long cost = (M + N - 1) / N;
        if (cost > X)
            break;
        X -= cost;
        N += M / N;
    }
    cout << N << "\n";
    return 0;
}