Codeforces 1373 F. Network Coverage —— 想法，贪心

This way

题意：

现在有n个城市围成一个环，每个城市有ai个家庭需要供电，并且每个城市有一个发电厂，可以供给第i和第i+1个城市共bi个家庭的电。问你每个家庭是否都能得到电。

题解：

那么我们首先选择一个i，要求是bi>=ai。 那么我们假设bi首先满足ai，然后多的供给给下一个城市，这样做一遍，很明显中间会有不够的地方，此时我们就需要让选择的这个起始城市多供给给缺的部分。 那么假设所有缺的加起来为mx，如果mx>ai的话，bi就算将bi全部都传递过去也不够，所以这种情况不行。 如果mx<=ai，那么就表示有戏，我们就让bi少传递mx给ai，将mx的电传递到下一个。那么此时bi传递给ai的电就是ai-mx，于是ai就还需要mx格电，此时我们设传递的电的数量为bi-ai+mx,将ai置为mx，bi置为0. 然后再做一遍，如果不行就是真的不行，中间一定有断点使得bi的电传不过去。 时间复杂度应该是$O(n)$的，但是可能常数太大导致花了700ms左右，时间复杂度应该可以优化，但没必要。

#include<bits/stdc++.h> using namespace std; #define ll long long const int N=1e6+5; ll a[N],b[N]; int n; int main() { int t; scanf("%d",&t); for(int tim=1;tim<=t;tim++){ scanf("%d",&n); for(int i=0;i<n;i++) scanf("%lld",&a[i]); int sta=-1; for(int i=0;i<n;i++) scanf("%lld",&b[i]),sta=b[i]>=a[i]?i:sta; if(sta==-1){ printf("NO\n"); continue; } ll res=0,mx=0; for(int i=sta;i<=sta+n-1;i++){ int u=i%n; if(b[u]+res>=a[u]) res=min(b[u],res+b[u]-a[u]); else mx+=a[u]-b[u]-res,res=0; } if(mx){ if(mx>a[sta]){ printf("NO\n"); continue; } res=b[sta]-a[sta]+mx; a[sta]=mx; b[sta]=0; mx=0; for(int i=sta+1;i<=sta+n;i++){ int u=i%n; if(b[u]+res>=a[u]) res=min(b[u],res+b[u]-a[u]); else{ mx=1; break; } } if(mx) printf("NO\n"); else printf("YES\n"); } else printf("YES\n"); } return 0; }