CodeForces - 1373F Network Coverage(二分)

题目链接：点击查看

题目大意：给出一个首尾相接的环，每个点的编号分别为 1 ~ n ，其中每个点的需求量记为 a[ i ] ，供应量记为 b[ i ] ，每个点可以用 b[ i ] 向 a[ i ] 和 a[ i + 1 ] 提供需求，现在问是否存在着一种分配方案，使得每个点的需求 a[ i ] 都能得到满足

题目分析：题解的 O( n ) 解法表示没看懂，还是说一下从网上看到的二分解法吧

假设任意一个点 b[ i ] 向 a[ i ] 或者 a[ i + 1 ] 的供应量确定了的话，那么剩下的 n 个点的分配策略通过贪心是可以确定的，贪心策略无非就是：如果上一个点有剩余，那么优先用上一个点剩下的来提供给 a[ i ] ，还有不足的话再用 b[ i ] 提供

再观察一下 b[ i ] 向 a[ i ] 的供应量 x 有什么性质吧，如果 x 非常小，极限情况为 0 时，那么如果转了一圈回到点 i - 1 结束时，此时剩余的量记为 remain ，如果 remain + x < a[ i ] 的话，那么说明 x 太小了，需要加大 x 才能使得前面的不等式满足，同理如果 x 非常大的话，也就是说 b[ i ] 全部给 a[ i ] 提供的话，这样 remain + x >= a[ i ] 这个式子也更容易满足了，但可能还没有回到点 i - 1 时，在路上的其中的某一点可能 a[ j ] 的供给就不够了

综上所述，当 x 特别小时可能不行，特别大时也可能不行，这样我们只需要打一下标记，然后去二分这个 x 就好了

为了方便处理，我二分的是 b[ n ] 对 a[ n ] 的提供量

代码：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e6+100;int a[N],b[N],n;int check(int mid) {int remain=b[n]-mid;//b[n]向a[1]提供多少 for(int i=1;i<n;i++){int ta=a[i],tb=b[i];ta-=min(ta,remain);//a[i]优先用上一次剩下的 tb-=ta;//不足的再用本次的b[i]来补齐if(tb<0)//断流了 return -1; remain=tb;}//最后的remain是b[n-1]可以给a[n]提供的return remain+mid>=a[n]; }int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--){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];//二分b[n]向a[n]提供多少bool flag=false;while(l<=r){int mid=l+r>>1;int t=check(mid);if(t==1){flag=true;break;}else if(t==-1)//出现断流，需要b[n]多向a[1]提供点，说明b[n]向a[n]提供的太多了r=mid-1; else//最后剩下的加上当前的mid小于a[n]，需要b[n]多向a[n]提供点 l=mid+1;}if(flag)puts("YES");elseputs("NO");}return 0; }

 

超强干货来袭 云风专访：近40年码龄，通宵达旦的技术人生

总结

以上是生活随笔为你收集整理的CodeForces - 1373F Network Coverage(二分)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。