6.26CF模拟赛B:数组缩减题解

题目描述

链接

CF模拟赛B:数组缩减

文字描述

B. 数组缩减
time limit per test1 s.
memory limit per test256 MB
inputstandard input
outputstandard output
Kristina has two arrays a and b, each containing n non-negative integers. She can perform the following operation on array a any number of times:

Kristina 有两个数组 a and b，每一个都包含 n 个非负整数。她可以对 a 数组进行如下操作任意多次：

对数组中每一个非 0 元素减 1，即将所有大于 0 的 ai 替换成 ai−1 (1≤i≤n)。如果 ai 是 0, 它的值不变.
Determine whether Kristina can get an array b from an array a in some number of operations (probably zero). In other words, can she make ai=bi after some number of operations for each 1≤i≤n?

判断Kristina能否通过若干次（可以是 0 次）操作将 a 数组变成 b 数组？换句话说，她能否在若干次操作后让 ai=bi 对于任意 1≤i≤n 成立？

For example, let n=4, a=[3,5,4,1] and b=[1,3,2,0]. In this case, she can apply the operation twice:

after the first application of the operation she gets a=[2,4,3,0];
after the second use of the operation she gets a=[1,3,2,0].
例如对于 n=4, a=[3,5,4,1] 和 b=[1,3,2,0]，她可以通过两次操作：

第一次操作之后 a=[2,4,3,0];
第二次操作之后 a=[1,3,2,0].
Thus, in two operations, she can get an array b from an array a.

于是经过两次操作，她可以把 a 变成 b。

Input
The first line of the input contains an integer t (1≤t≤104) —the number of test cases in the test.

第一行包含一个整数 t (1≤t≤104) — 代表测试数据组数。

The descriptions of the test cases follow.

每组数据的描述如下。

The first line of each test case contains a single integer n (1≤n≤5⋅104).

第一行包含一个整数 n (1≤n≤5⋅104)。

The second line of each test case contains exactly n non-negative integers a1,a2,…,an (0≤ai≤109).

第二行包含 n 个非负整数 a1,a2,…,an (0≤ai≤109)。

The third line of each test case contains exactly n non-negative integers b1,b2,…,bn (0≤bi≤109).

第三行包含 n 个非负整数 b1,b2,…,bn (0≤bi≤109)。

It is guaranteed that the sum of n values over all test cases in the test does not exceed 2⋅105.

数据保证 所有测试数据的 n 之和不超过 2⋅105。

Output
For each test case, output on a separate line:

YES, if by doing some number of operations it is possible to get an array b from an array a;
NO otherwise.
You can output YES and NO in any case (for example, strings yEs, yes, Yes and YES will be recognized as a positive response).

对于每组测试数据，输出YES 或者NO。

Example
inputCopy
6
4
3 5 4 1
1 3 2 0
3
1 2 1
0 1 0
4
5 3 7 2
1 1 1 1
5
1 2 3 4 5
1 2 3 4 6
1
8
0
1
4
6
outputCopy
YES
YES
NO
NO
YES
NO
Note
The first test case is analyzed in the statement.

对于第一组测试数据，已经在题面描述中分析了。

In the second test case, it is enough to apply the operation to array a once.

对于第二组测试数据，一次操作足矣。

In the third test case, it is impossible to get array b from array a.

对于第三组测试数据，不能从 a 变成 b。

题目分析

1. 此题复杂数据较多，一点一点分析
2. 首先判断 b[i]>a[i]只要有一个NO下一组
3. b[i]全是0，YES下一组
4. b[i]！=0 的a[i]-b[i]有一个不同NO下一组
5. b[i]==0的a[i]-b[i]>(4.)NO下一组，否则YES下一组

代码实现

#include<bits/stdc++.h>
using namespace std;

const int maxn=5e4+10;
int t,n,cnt;
int a[maxn],b[maxn];
int main(){
    
	scanf("%d",&t);
	while(t--){
    
		//2
		int flag=1;
		cnt=-1;
		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]);
			if(b[i]!=0)flag=0;
		}
		if(flag){
    
			printf("YES\n");
			continue;
		}
		//3
		flag=1;
		for(int i=1;i<=n;i++){
    
			if(b[i]>a[i]){
    
				flag=0;
				break;
			}
		}
		if(!flag){
    
			printf("NO\n");
			continue;
		}
		//4
		flag=1;
		for(int i=1;i<=n;i++){
    
			if(b[i]!=0){
    
				if(cnt==-1)cnt=a[i]-b[i];
				else {
    
					if(cnt!=a[i]-b[i]){
    
						flag=0;
						break;
					}
				}
			}
		}
		if(!flag){
    
			printf("NO\n");
			continue;
		}
		//5
		flag=1;
		for(int i=1;i<=n;i++){
    
			if(b[i]==0){
    
				if(cnt<a[i]-b[i]){
    
					flag=0;
					break;
				}
			}
		}
		if(flag)printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}