环形资源分配

Posted on | In

https://codeforces.com/contest/1373/problem/F

这题感觉出的很棒，感觉很简洁经典的题面，却从未见过（可能是做题太少）。

有环形的n个城市、n个资源站交替排布，每个城市需要资源ai，每个资源站最多能提供资源bi（只能给它两侧的城市ai、ai+1提供）。问能这n个城市的需求能否得到满足。1e6

这题一看很明显就知道能通过某种很妙的算法扫一遍就行，但比赛中想不到（；´д｀）ゞ。后来题解出来瞟了一眼就瞬间明白。

首先我们从任意位置开始向右扫，在满足必须需求need的基础上把bi都给右侧；必要需求是什么呢？就是当前bi左侧的ai剩余未满足的部分，这部分是一定要由bi向左补足的，因为我们bi的给予从一开始是优先向右，等于牺牲了a1，如果这样的条件下ai都不能被满足，那么就不会有成功的情况了。同时我们需要维护最多能“回流”多少资源res，这是因为对于有的bi，可能在满足左侧必要需求，并把右侧ai+1，全部满足之后还有剩余，那么就可以考虑把它向左回流，减轻bi-1的负担，这样一路回流到a1。然后我们执行完bn后，这时已计算出a1（n+1）的need，然后比较，如果res>=need的话就成功，这表明我们在满足a2-n都满足的情况下，能够向左返还给b1、使得b1能向左分配的资源，比给a1提供bn资源后剩下未满足的部分要多或等于，即所有a全部满足。

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
39
40
41
42
43
#include<bits/stdc++.h>
using namespace std;

const int maxn=1e6+4;

#define ll long long

ll a[maxn],b[maxn];

int main(){
    std::ios::sync_with_stdio(false);
    int t,n;
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        for(int i=1;i<=n;i++)
            cin>>b[i];
        a[n+1]=a[1];
        bool ans=true;
        ll need=0,res=0,add=0,extra=2e9;
        for(int i=1;i<=n;i++){
            if(b[i]<need){
                ans=false;
                break;
            }
            b[i]-=need;
            extra=min(extra,a[i]-need);
            if(b[i]>a[i+1]){
                ll left=b[i]-a[i+1];
                add=min(extra,left);
                extra-=add;
                res+=add;
                need=0;
            }else{
                need=a[i+1]-b[i];
            }
        }
        ans=ans&(res>=need);
        cout<<(ans?"YES":"NO")<<endl;
    }
}