Codeforces 1341 C

题意： 阅读理解题。读了三十多分钟才明白大意。
给定一个序列，问按照从 $1$1到 $n$n的顺序放置这 $n$n个数。
假设这 $n$n个数分 $k$k次放置，每次从第 n−(j=1∑​i​ $s\left[j\right])+1$s[j])+1开始放置 $s\left[i\right]$s[i]个数，
要求这 $s\left[i\right]$s[i]个数的范围为 [j=1∑​i−1​ s[j]+1,j=1∑​i​ $s\left[j\right]]$s[j]]。

举个例子：如序列 $\{4,5,6,7,2,3,1\}${4,5,6,7,2,3,1}，那么第一组为： $\left\{1\right\}${1}，第二组为 $\{2,3\}${2,3}，第三组为： $\{4,5,6,7\}${4,5,6,7}，我们按照顺序依次在第 $[7,7]$[7,7]放入了 $1$1， $[5,6]$[5,6]放入了 $2,3$2,3， $[1,4]$[1,4]放入了 $4,5,6,7$4,5,6,7。

题解： 可以发现对于给定序列如果是合法的，那么对于任意的 $a\left[i\right]-a[i-1]\le 1$a[i]−a[i−1]≤1。
证明： 若存在合法的序列，其相邻的数字之差大于 $1$1，
那么必然存在有相邻的两个数 $x,x+dif,dif>1$x,x+dif,dif>1，其中 $pos[x+dif]-pos\left[x\right]=1$pos[x+dif]−pos[x]=1。
首先，由于每组内是按照升序放置的，故组内不会出现相邻数字差 $>1$>1的情况，故这必然存在于不同组的边界间。若两组间边界相差大于 $1$1，即两组之间必然存在至少一个数在两组被放置后仍未被放置。
假设第一组数为 $[x,x+1,x+2,...y-2]$[x,x+1,x+2,...y−2]，第二组数为 $[y,y+1,y+\mathrm{2...},n]$[y,y+1,y+2...,n]
那么由于 $y-1$y−1这个数未被放置，但是按照我们的分组要求，如果实际给出序列满足上面的两组连续，则 $y-1$y−1必然可以使得两组数连接成为一组。那么如果真的存在如上的序列，其必然是不合法序列。

代码：

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

const int N = 1e5 + 10;
int q[N], n;

void solve() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) scanf("%d", &q[i]);
	
	for(int i = 2; i <= n; i++)
		if(q[i] - q[i - 1] > 1) {
			puts("No");
			return ;	
		} 
	puts("Yes");
}

int main()
{
	int T = 1;
	scanf("%d", &T);
	while(T--) solve();
	
	return 0;
}