雇佣兵

题意

雇佣兵每次必须把体力补满 $M$ 才能战斗。每个能量元素至多恢复当前战斗力 $N$ 的体力；战斗 $M$ 天后，战斗力增加 $\lfloor M/N \rfloor$ 。给定能量元素数，求最终最大战斗力。

思路

一次战斗期前至少需要 $\lceil M/N \rceil$ 个能量元素，即 (M + N - 1) // N。能量不足时无法开始新的战斗期，循环结束。

若能开始，就扣除这些元素，并按本期开始时的战斗力增加 M // N。更新必须在扣除能量后进行，但两个公式都使用本期旧的战斗力。

代码

Python代码

python

1
2
3
4
5
6
7
8
9
10
11
12maximum_stamina, combat_power, energy = map(int, input().split())

while True:
    # 每个元素至多恢复当前战斗力，需要向上取整计算元素数。
    energy_needed = (maximum_stamina + combat_power - 1) // combat_power
    if energy < energy_needed:
        break

    energy -= energy_needed
    combat_power += maximum_stamina // combat_power

print(combat_power)

C++代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36/*============================================================================
* Title : openjudge 
* Author: Rainboy
* Time  : 2017-03-19 09:18
* update: 2017-03-19 09:18
* © Copyright 2017 Rainboy. All Rights Reserved.
*=============================================================================*/

#include <cstdio>
int m,n,x;

int fight_up(int n,int m){
    return m / n;
}

int use_x(int n,int m){
    int ans = m / n;
    if( m %n != 0 )
        ans++;
    return ans;
}

int main(){
    scanf("%d%d%d",&m,&n,&x);
    while(1){ // 能量元素不用完
        
        //1.使用x
        x -= use_x(n,m);
        if(x <0)
            break;
        //2. n上升
        n +=fight_up(n,m);
    }
    printf("%d",n);
    return 0;
}

复杂度

设能完成的战斗期数为 $t$ ，时间复杂度为 $O(t)$ ，额外空间复杂度为 $O(1)$ 。

总结

按“能否开始一个完整周期”模拟时，先计算本期资源需求，再决定是否更新状态。

目录

题意

思路

代码

Python代码

C++代码

复杂度

总结