一个题解

· · 题解

提供一种不一样的二分，不用前缀和 (〃´-ω･)/。

显然初始力量是单调性的，力量越多显然越能打，所以可以考虑二分。

思路 (不很清楚谅解一下)

这个二分的 check 比较特殊，不用把怪物看成环，下面我们以第二个样例为例，来讲述一下这个方法（这个 check 我不太会讲所以我举例）：

怪物强度：1 6 3 3 2\ 打怪收益：1 2 1 0 2

这个时候我们不妨假设我们的初始力量为 3（就当是二分到的）

我们就从第一个位置开始，怪物强度只有 1，显然能干掉，我们就先干掉试试，反正没负收益（如果我们能在这里开始把后面的怪物打掉明显比之后再到终点回来打是不劣的）。\ 力量也变强了 1 点，但还不能打败第二个怪物，那我们新开一个存档，从第三个怪开始打，剩下两个怪物秋后算账。\ 很顺利，下面三个怪物都清掉了，我们回到开头，发现剩下的怪也能清掉，那么这就说明了初始力量为 3 是能把怪物清掉的。

再假设初始力量为 1

我们重复上面的流程，发现没有一种起点能打到底，所以 1 不行。

在最后一个怪开始能打到底，但回去从开头打的话会有打不掉的怪，，所以 2 也不行。

code

如果还有不理解的地方可以看看这里：

:::success[代码]

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5 * 114514;
int n;
int a[N];
int b[N];
bool check(int x){
    int rj = 0;
    int sum = 0;
    for(int i = 1;i <= n;i ++ ){
        if(x >= a[i]){
            int j;
            int tmp = x;
            for(j = i;j <= n;j ++ ){
                if(tmp >= a[j]){
                    tmp += b[j];
                }
                else{
                    break;
                    //打不过，重新找起点
                }
            }
            if(j > n){
                rj = i;
                sum = tmp;
                //我找到起点了
                break;
            }
            i = j - 1; // 不是我能打过的怪，直接跳过
        }
    }
    if(rj == 0) return 0; //打不到底
    for(int i = 1;i < rj;i ++ ){
        if(sum < a[i]) return 0;
        sum += b[i];
    }
    return 1;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for(int i = 1;i <= n;i ++ ){
        cin >> a[i];
    }
    for(int i = 1;i <= n;i ++ ){
        cin >> b[i];
    }
    int lft = 0;
    int rgt = 1e9 + 5;
    int ans = rgt;
    while(lft <= rgt){
        int mid = lft + rgt >> 1;
        //二分初始力量
        if(check(mid)){
            rgt = mid - 1;
            ans = mid;
        }
        else{
            lft = mid + 1;
        }
    }
    cout << ans << endl;
    return 0;
}

:::