CF1329F题解

能发现：

1.输出序列与掉落顺序没有任何关系（因为单调性不会被改变）。

2.输出的序列 $h_i$ 最多有一组 $h_i=h_{i+1}$。

对 2 的证明：

当 $h_{i+1}$ 与 $h_{i}$ 奇偶性相同时，$h_{i+1}$ 向 $h_i$ 的数次掉落会使 $h_i=h_{i+1}$ 。
当 $h_{i+1}$ 与 $h_i$ 奇偶性不同时，$h_{i+1}$ 向$h_i$ 的数次掉落会使 $h_i+1=h_{i+1}$ ，此时由于原先奇偶性不同，所以此时的 $h_i$ 与 $h_{i-1}$ 奇偶性相同，执行2。

对于会掉落的 $h_i$ ，其掉落的本质是：

如果 $i=1$ 或者 $h_{i+1}<h_i+2$ ，停止。
否则 $h_i\gets h_i+1$ ，$h_{i+1} \gets h_{i+1}-1$ ，$i \gets i-1$ 。

那么

如果 $h_i$ 左边的数互不相等，那么掉落会一直到 $i=1$ ，过程中一定会使得 $h_i=h_{i+1}$ 。

否则，若存在$h_i=h_{i+1}$，则掉落会在$h_{i+1}$处停止，此时相等的个数减少$1$个或不变（连续三个同奇偶时不变）。

那么从$h_n$开始掉落，无论是过程中还是最后都不可能存在$1$对以上的相等。

设$sum=\sum h_i$

由于上面的结论，所以只有唯一一个序列满足：

其差分序列中均为 $0$ 或 $1$ 且 $0$ 至多有一个。
长度为 $n$ 且和为 $sum$ 。

那么

$ 2sum=n(2h_1+n-1) $ ，可以求出 $h_1$ ，通过序列 ${1,2,3......n}$ 开始构造这个序列，直到其总和为 $\sum h_i$ 。

#include<bits/stdc++.h>

main()

{

	int n;

	scanf("%d",&n);

	long long h,s=-n*((long long)n-1)/2;

	for(int i=0;i<n;++i)

		scanf("%lld",&h),s+=h;

	for(int i=0;i<n;++i)

		printf("%lld ",i+s/n+(i<s%n));

}

巴特西

CF1329F题解

最新文章

热门文章