「PR #12」电塔

首先考虑小小地转化题意：我们知道第 \(i\) 座电塔的终点 \(y_i\) 必然大于等于 \((i-1)d\)，并且 \(y_i-(i-1)d\) 是单调不降的。所以我们将 \(x_i\leftarrow x_i-(i-1)d\) 然后求一个单调不降的非负整数序列 \(a\) 并最小化 \(\sum\limits_{i=1}^n|x_i-a_i|\)。这是一个经典题。我们考虑如下做法（下面部分翻译自洛谷题解）：

令 \(f_{i,j}\) 表示选了前 \(i\) 个数，并且第 \(i\) 个数小于等于 \(j\) 时的前 \(i\) 项之和的最小值。那么转移时这样的：

• \(f_{i,j}\leftarrow f_{i-1,j}+|x_i-j|\)。

• 对 \(f_{i,j}\) 取前缀最小值。

那么实际上我们的 \(f_{i,j}\) 是关于 \(j\) 的单调不增函数，并且斜率单调不减，且最大斜率必然为 \(0\)。

那么考虑对这样的一个函数维护其所有拐点（为了方便，我们将不存在的斜率也维护一下拐点，例如 \(9,6,5\) 我们将第二个数同时看作 \(-3\) 到 \(-2\) 的拐点与 \(-2\) 到 \(-1\) 的拐点），然后考虑加上一个绝对值函数，并取前缀最小值所带来的影响。

加上绝对值函数，我们只需要在拐点集合里加入两个 \(x_i\) 即可。然后取前缀最小值就是把最后一段斜率为 \(1\) 的推平，也就是去掉最大的拐点。发现拐点集合用 STL 就可以维护了。至于考虑答案，我们在最后取出最大拐点，这一定是 \(a_n\) 的值。然后我们再推出 \(a_{n-1}\) 的值，这个可以比较 \(a_n\) 与上一次最大拐点的值的较小者就可以了。总复杂度 \(\mathcal O(n\log n)\)。注意细节，因为是非负整数，所以要注意一下 \(x_i<0\) 的情况。