题目链接：点击查看

题目大意：给出一个首尾相接的环，每个点的编号分别为 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");
		else
			puts("NO");
	}










    return 0;
}