Educational Codeforces Round 90 F. Network Coverage 二分

题目链接：https://codeforces.com/contest/1373/problem/F
题目大意：有n个环形城市。每个城市对网络的需求数是a[i]。每个城市都可以修建网络塔。提供b[i]个网络。在b[i]修建的网络塔只能供a[i], a[i+1]使用。现在问是否通过合理的分配可以满足所有城市的网络需求。
思路：我们假设b[n]给a[1]分配了x个。如果x小了。导致[1, n-1]中间发现不够用. 如果x大了。发现在b[n]处不够用。那么就可以对x进行二分了。

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

int a[1000005], b[1000005];

int check(LL x, int n){
    int y=x;
    for(int i=1; i<n; i++){
        x=x+b[i]-a[i];
        x=min(x, 1ll*b[i]);
        if(x<0){
            return -1;
        }
    }
    if(x+b[n]-y>=a[n]){
        return 0;
    }
    else{
        return 1;
    }
}

int main() {

    int t; scanf("%d", &t);
    while(t--){
        int n; scanf("%d", &n);
        for(int i=1; i<=n; i++){
            scanf("%d", &a[i]);
        }
        for(int i=1; i<=n; i++){
            scanf("%d", &b[i]);
        }
        int l=0, r=b[n], f=0;
        while(l<=r){
            int mid=l+r>>1;
            int k=check(mid, n);
            if(k==0){
                printf("YES\n");
                f=1;
                break;
            }
            if(k<0){
                l=mid+1;
            }
            if(k>0){
                r=mid-1;
            }
        }
        if(!f){
            printf("NO\n");
        }
    }

    return 0;
}