Codeforces Round #637 (Div. 2) C. Nastya and Strange Generator（阅读理解/思维）
题目链接
1.题目大意：给出一个序列，问能否构造出这个序列。首先要构造数组为空，构造过程如下：
在第
i
i
i步，我们只能向序列中填入数字
i
i
i。被构造数组
a
a
a的每个位置
j
j
j，
[
j
,
n
]
[j,n]
[j,n]中第一个为空的位置，那么对应
r
r
r数组就是其位置，那么一开始
a
a
a数组均为空，
r
r
r数组就是{1,2,3,4,5}，
c
o
u
n
t
count
count数组记录这些位置每种出现多少次，即{1,1,1,1,1}。每次选择出现次数最多的位置，那么这时我们选择位置
5
5
5，那么数字
1
1
1就填入数组，即此时的
a
a
a数组为{?,?,?,?,1}；然后数组
r
r
r为{1,2,3,4,×}（×代表没有），
c
o
u
n
t
count
count数组为{1,1,1,1,0}…
2.第一次写这种构造题写吐了，完全不知所然。看了题解慢慢地懂了，按照上面的步骤，我们将数字 i i i填入位置 p o s pos pos后，那么如果 p o s < n pos<n pos<n，如果位置不被占用的话下一个被填的位置一定为 p o s + 1 pos+1 pos+1，则此时填的数字为上一个数字加 1 1 1；如果较大的位置被较小的数字占用了，那么会出现第二个数比第一个数小的情况，也同样可以满足，如4 3 1 2
3.那么最后的规律就是要么 a [ i + 1 ] a[i+1] a[i+1]等于 a [ i ] + 1 a[ i ]+1 a[i]+1要么 a [ i + 1 ] < a [ i ] a[i+1]<a[i] a[i+1]<a[i]，即 a [ i + 1 ] a[i+1] a[i+1]比于 a [ i ] a[i] a[i]大 2 2 2及以上
#include <iostream>
using namespace std;
const int maxn=2e5+10;
int a[maxn];
int n,t;
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>t;
while(t--){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
int flag=1;
for(int i=2;i<=n;i++){
if(a[i]-a[i-1]>1){
flag=0;
break;
}
}
if(flag) puts("Yes");
else puts("No");
}
return 0;
}