描述

小Ho的虚拟城市正在遭受小Hi的攻击，小Hi用来攻击小Ho城市的武器是一艘歼星舰，这艘歼星舰会以T(T为大于0的整数)个单位时间的间隔向小Ho的城市轰击。歼星舰总共有N枚炮弹，其中第i枚会造成Ai点伤害值。

幸好小Ho的城市有K层护盾，每层护盾可以抵挡M点伤害。当某次轰击使得伤害值达或超过M时，该层护盾就会被击碎；该次轰击溢出的伤害不会作用于下一层护盾；下一次轰击将由下一层护盾承受。

同时，受损但尚未被击碎护盾会以每单位时间减少1点伤害值的速度修复自己，直到伤害值降为0。这就意味着小Hi的攻击间隔T越大，小Ho撑过这N枚炮弹的可能性就越大。

那么问题来了，小Hi的攻击间隔T至少需要是多少，小Ho城市的防护护盾才能不被全部击破？

为了使题目不存在歧义，规定：

小Hi的第i次攻击发生在时刻(i-1)*T

小Ho的第i次修复发生在时刻i-0.5

输入

第一行包含3个整数N、M和K，意义如前文所述。

第二行包含N个整数A1 - AN，表示小Hi第i枚炮弹的伤害值。

对于30%的数据，满足N<=100

对于100%的数据，满足1<=N<=100000

对于100%的数据，满足1<=K<=10, 1<=Ai, M<=100000

输出

输出使得小Ho城市的防护护盾不被全部击破的小Hi攻击间隔的最小值。如果不存在这样的T，则输出-1。

样例输入

3 5 1
3 3 3

样例输出

3

思路

这道题的关键条件是护盾可以回血(参考一下星际争霸中的神族单位)。

所以攻击间隔越大，护盾可能的回血就越多。如果小Hi的攻击中伤害值大于等于M的炮弹少于K发，那么如果攻击间隔过大，即便N发总伤害超过KM，也可能最终不能击破全部护盾。

题目要求出可以使护盾不被全部击破的攻击间隔最小值。这个值显然是可以二分的。从[0, M]之中二分，判断当前的间隔T会不会导致护盾全破可以通过O(N)的模拟计算得到。

所以总复杂度是O(NlogM)

提交了很多次，没有注意到T是大于0的整数，攻击需要间隔。

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
37
38
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int N, M, K, A[100005];
    cin >> N >> M >> K;
    for(int i = 0; i < N; i++) cin >> A[i];
    int L = 0, R = M, ans = -1;
    while(L <= R) { //二分这里老是搞不懂要不要等号，现在明白了，举例子一直往一边取值，必须等号才能取到边缘值
        int mid = (L + R) / 2;
        int cnt = K, value = M;
        bool flag = true;
        for(int i = 0; i < N; i++) {
            if(A[i] >= value) { //如果当前的炮弹的伤害大于等于护盾，护盾破坏
                cnt--;
                value = M;
            }
            else{   //否则护盾受到伤害并回血
                value = value - A[i] + mid;
                if(value > M) value = M;
            }
            if(cnt == 0) {  //没有护盾了
                flag = false;
                break;
            }
        }
        if(flag) {  //护盾还存在，间隔值过大
            R = mid - 1;
            ans = mid;
        }
        else L = mid + 1;   //一定要记得加减1
    }
    if(ans == 0) cout << 1 << endl;
    else if(ans != -1) cout << ans << endl;
    else cout << -1 << endl;
    return 0;
}