P4331 [BalticOI 2004] Sequence 数字序列

li_cat · 2025-06-02 17:52:33 · 个人记录

思路

转化序列

因为严格递增的条件不太好处理，可以试着转成非降

假设我们将 b 转化为 b' ，经过我们转化过的 b' 是一条所有值均相等的数列，但是当它转换为要输出的 b 时是一条严格递增的数列

不难发现，当 b_i=b'_i+i(1\le i\le n) 时可以满足 (如果觉得很难发现就记下来这个结论，以后也能不难发现了)

于是就可以知道我们要用来处理的 b'_i=b_i-i

但是绝对值之差不能改变，所以对应的 a'_i=a_i-i

中位数的性质

结论

当 a' 在一段区间上单调不增的话，那么令这段区间上的所有 b' 都为这段序列的中位数可以使得|a'_i-b'_i|之和最小

并不严谨的证明

几何上可以口胡一个证明

首先，必然需要一个交点，没有交点的话整体平移到一个交点可以使其更优

其次，一个显而易见的是，此时的 b' 在这一段上只能是平的，因为一旦倾斜就可以把它压平得到更优解

当选取一个点 b'_i 作为交点时，往中位的方向移动可以使得解更优，于是最后就会移到中位数的位置了

合并

当两段全取中位数且相邻的区间 b 合并时，有两种情况

• 左边的每一个数都大于右边，此时要把答案转为整体的中位数
• 左边的每一个数都小于右边，此时直接放一起就好了，相当于没有合并

可以用可并堆来维护，每次合并完之后把元素弹到只剩长度 len/2+1 即可

这个过程可以在一个栈里完成

时间复杂度 O(n\log n)