CF549G Happy Line 做题记录

给定一个 $n$ 个元素的整数序列 $a$, 任意时刻对于任一对相邻元素 $(a_{i-1},a_i)$，若 $a_{i-1} > a_{i}$ 则要依次执行如下操作：

a[i-1]--,a[i]++，然后交换 $a_{i-1}$ 和 $a_i$ 的位置。

经过若干次操作后，若能使整个序列变成非降的，则输出最终的序列；否则输出 :( 。

$1 \leq n \leq 2\times 10^5, 0 \leq a[i] \leq 10^9$。

以后看到这种操作中带加一减一的都要考虑减掉下标。

设 $b_i=a_i-i$，不难发现一次操作 $(i,i+1)$ 相当于交换了 $b_i$ 和 $b_{i+1}$。

那么对 $b_i$ 排序，判断是否两两不同即可。