题目链接

题意分析

我就是死在了这道题上

首先我们可以明白的是 所有\(a_i\)增加的上限就是\(lim=Min_{1≤i≤n}b_i\)

然后我们令\(c_i=lim-b_i\)

如果存在\(c_i<0\)的话 那是绝对不符合要求的

这样的话我们的操作就变成了

1.选择一个\(k(1≤k≤n)\)使得所有\(c_1,c_2,...,c_k\)全部\(-1\)

2.选择一个\(k(1≤k≤n)\)使得所有\(c_k,c_{k+1},...,c_n\)全部\(-1\)

然后的话 我们就是躲过这两种操作使得所有\(c_i\)相等并且都是\(≥0\)

当时想到了这里 然后就走歪了 但是当时也明白 这道题的正解应该是比较简单的

但是真正看到正解的那一刻 我还是震惊到了

整体加减 我们想到了什么 差分！！！

我们让\(c_0=0\) 然后的话\(d_i=c_i-c_{i-1}(1≤i≤n)\)

然后我们再回头看这两种操作

1.选择一个\(k(1≤k≤n)\)使得\(d_1-1,d_{k+1}+1\)

2.选择一个\(k(1≤k≤n)\)使得\(d_k-1\)

然后的话 我们就是看看

\[d_1 + \sum_{i=2}^n{[d_i<0]d_i}≥0 \]

这样的话就可以了

CODE:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cmath>
#define N 1000080
using namespace std;
int T,n,lim,tot;
bool flag;
int cdy[N],wzy[N],num[N],d[N];
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);lim=2100000000;flag=0;tot=0;
		for(int i=1;i<=n;++i) scanf("%d",&cdy[i]);
		for(int i=1;i<=n;++i) scanf("%d",&wzy[i]);
		for(int i=1;i<=n;++i) lim=min(lim,wzy[i]);
		for(int i=1;i<=n;++i) num[i]=lim-cdy[i];
		for(int i=1;i<=n;++i) if(num[i]<0) {flag=1;break;}
		if(flag) {puts("No");continue;}
		for(int i=1;i<=n;++i) d[i]=num[i]-num[i-1];
		for(int i=1;i<=n;++i)
		if(i==1) tot+=d[i];
		else if(d[i]<0) tot+=d[i];
		if(tot>=0) puts("Yes");
		else puts("No"); 
	}
	return 0;
}