时间限制 \(1s\) | 空间限制 \(250M\)
题目大意
题目描述
给定一个数列 \(a_{1…n}\), 如果满足下面条件, 你可以使 \(a_i = a_i + 1\):
- \(i < n\) 且 \(a_i \leq a_{i+1}\)
- \(i = n\) 且 \(a_i \leq a_{1}\)
再给定一个数列 \(b_{1…n}\), 问 \(a\) 是否可以通过上述操作变为 \(b\).
输入格式
本题多测.
第一行为 \(t\), 表示 \(t\) 组数据.
接下来 \(t\) 组数据，每组第一行为一个正整数 \(n\),
第二行为 \(n\) 个整数, 代表数列 \(a\);
第三行为 \(n\) 个整数, 代表数列 \(b\).
保证 \(\Sigma n \le 2×10^5\).
输出格式
对于每组数据,输出 "YES" 或 "NO".
| 输入数据 | 输出数据 |
|---|---|
| 5 3 1 2 5 1 2 5 2 2 2 1 3 4 3 4 1 2 6 4 2 5 3 2 4 1 4 5 3 5 1 2 3 4 5 6 5 6 7 6 |
YES NO NO NO YES |
（感谢kjc提供的思路
思路
由如下两个条件：
- \(i < n\) 且 \(a_i \leq a_{i+1}\)
- \(i = n\) 且 \(a_i \leq a_{1}\)
可以推出，如果\(a\)可以通过若干次操作形成\(b\)，那么他们一定满足：
-
很明显，\(a_i \leq b_i\)
-
那么，根据第二个条件，可以发现每个\(a_{i}\)最大只能变成\(a_{i+1}+1\)，所以同理到数组\(b\)也应满足：\(b_{i}\leq b_{i+1}+1\space (a_i \neq b_i)\)
代码
#include<bits/stdc++.h>
using namespace std;
const int Maxn=2e5+10;
int a[Maxn],b[Maxn];
int n,flag;
void run()
{
cin>>n;flag=1;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++)
{
cin>>b[i];
if(b[i]<a[i]) flag=0;
}
for(int i=1;i<n&&flag;i++)
{
if(a[i]!=b[i] && b[i]>b[i+1]+1) flag=0;
}
if(b[n]>b[1]+1 && a[n]!=b[n]) flag=0;
for(int i=1;i<=n;i++)
{
if(a[i]!=b[i])
{
cout<<(flag?"YES":"NO")<<endl;
return;
}
}
cout<<"YES"<<endl;
}
int main()
{
int t;
cin>>t;
while(t--) run();
system("pause");
}