Shinju and the Lost Permutation（排列/构造/递增子序列）

题目 题意：给定一个排列 p p p，定义价值 c c c为数组 p p p的最大前缀和数组的取值数。比如 p = 4 , 3 , 2 , 5 , 6 , 1 p=4,3,2,5,6,1 p=4,3,2,5,6,1，最大前缀和数组则为 4 , 4 , 4 , 5 , 6 , 6 4,4,4,5,6,6 4,4,4,5,6,6，此时对应的 c = 3 c=3 c=3。现将数列 p p p循环向右移动， c i c_i ci​为第 i − 1 i-1 i−1个循环移动对应数列的价值， c 1 c_1 c1​表示原数列的价值。现给定数列 c 1 , . . . , c n c_1,...,c_n c1​,...,cn​，问是否存在对应的序列 p p p。

参考

首先，价值为1的序列，有且仅有一个，就是当前第一个数为n时， p 1 = n p_1=n p1​=n。 我们把 c c c数组重排，使价值为1的数做为首个元素。

其次，对于相邻元素，每次递增的值都是不会超过1的，最多增加1。即 c i + 1 − c i < = 1 c_{i+1}-c_{i}