序列排序 4

设选择位置 $i$ 的次数为 $x_i$。总操作次数会从所有元素中共同减去，不影响有序性。因此需要 $A_i+2x_i\leq A_{i+1}+2x_{i+1}$。令 $x_1=0$，依次取 $x_i=\max(0,x_{i-1}+\lceil(A_{i-1}-A_i)/2\rceil)$。增加前面的次数不会降低后面的下界，因此这一贪心选择最优。

每个 $x_i$ 不超过 $5\cdot10^8+50000$，因此总操作次数也不超过 $5.0005\cdot10^{13}$。所以可以用有符号64位整数类型精确计算答案。注意负数差值的向上取整除法。时间复杂度为 。

Solution written by GPT6