CF1141E Superhero Battle 题解

前言

这道题目其实就是 NOIP 2020 T4 微信步数 的40分做法。

这里提供 O( + )的做法 ------ 二分 + 前缀和(时间复杂度就是O(n))。

题目分析

不难发现，这道题目是要我们求最少多少天就会杀死怪物，同时，这个东西是具有单调性的。

（有解的情况下） 天数越多肯定就会扣除怪物越多的血量，所以我们可以采用二分。

同时，这个题目肯定许多情况会循环往复进行许多轮，所以我们二分的对象就是会进行多少轮。

具体做法

二分的话check函数就是二分的灵魂，往往check函数就会决定二分的复杂度。

采用前缀和优化后，我们可以找一个前缀和数组中的最小值 ？

求出来的 就是表示在同一轮的操作中能够扣除的血量最大值。

假设我们现在二分到的是第 轮 ， 那么我们判断 是否小于等于 即可。

不难发现，这个check函数我们是可以实现 O(1) 判断答案合法性的。

这样子我们就可以通过二分找到要轮多少轮啦。

最后扫一遍前缀和数组就可以获得答案了。

细节：

• 不需要轮许多轮，也就是第一轮就可以获得答案。
  判断 与 的大小关系即可。

• 在 不成立的情况下，也就是需要轮许多轮，但是我们发现轮完一轮得到的扣除怪物的血量为0,肯定无解。

• 判断无解的方式(最重要的一点):
  采用答案判断无解法，我们发现倘若题目给出的数据有解，答案肯定不会超过 ，否则就是无解。

Code

(代码里面有注释，因为笔者比较菜，题目分析可能不够详尽，看不懂题目分析就看看代码吧)

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 200005;
int n,H,M = 0x3f;
int sum[MAXN];

inline int read()
{
    int x = 0 , flag = 1;
    char ch = getchar();
    for( ; ch > '9' || ch < '0' ; ch = getchar()) if(ch == '-') flag = -1;
    for( ; ch >= '0' && ch <= '9' ; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
    return x * flag;
}

bool check(int x)
{
    if(x < 0ll)return 0;
    if(x * sum[n] + M + H <= 0ll) return 1;//O(1) check
    else return 0;
}

signed main()
{
    H = read() , n = read();
    for(int i = 1 ; i <= n ; i ++)
    {
        int x = read();
        sum[i] = sum[i - 1] + x;//累加前缀和
        M = min(M,sum[i]);//获得前缀和数组里面最小的一个
    }
    if(M + H <= 0ll)//这就是不需要进行多轮循环的情况
    {
        for(int i = 1 ; i <= n ; i ++)
            if(sum[i] + H <= 0ll ){cout << i ; break;}
        return 0;
    }
    if(sum[n] >= 0){cout << -1; return 0;}//假设需要多轮循环，但是每轮情况进行完使得怪物的血量增加或者不变，无解
    int Ans = -H / sum[n] + 5;//最多进行多少轮。
    for(int i = log2(Ans) ; i >= 0ll ; i --)
        if(check(Ans - (1ll << i))) Ans -= (1ll << i);
    int out = Ans * n;
    for(int i = 0 ; i <= n ; i ++)//一个小细节，从0开始枚举就是判断是否当前已经可以让怪物死了
        if(sum[i] + sum[n] * Ans + H <= 0ll) {out += i;break;}。
    if(out > (n + 1) * H)cout << -1;//根据得到的答案判断无解
    else cout << out;
    return 0;
}