洛谷P4331 [BalticOI 2004] Sequence 数字序列题解

题目链接：P4331 [BalticOI 2004] Sequence 数字序列

题意：

给定一个整数序列 \(a_1, a_2, \cdots , a_n\)，求出一个递增序列 \(b_1 < b_2 < ··· < b_n\)，

使得序列 \(a_i\) 和 \(b_i\) 的各项之差的绝对值之和 \(|a_1 - b_1| + |a_2 - b_2| + \cdots + |a_n - b_n|\) 最小。

输入格式：

第一行为数字 \(n (1≤n≤10^6)\)，接下来一行共有 \(n\) 个数字，表示序列 \(a_i (0≤a_i≤2^{31}-1)\)。

输出格式：

第一行输出最小的绝对值之和。

第二行输出序列 \(b_i\)，若有多种方案，只需输出其中一种。

数据范围：

\(1\le n\le 10^6 , 0\le a_i\le 2^{31}-1\)；

本题可以转化为另一个模型，即

给定序列 \(a_i\) ，每次可以将任意元素加 \(1\) 或减 \(1\) ，求使得序列严格递增的最小操作数。

令 \(a_i \gets a_i - i\) ，那么只需要单调不降即可。

设 \(f(i,j)\) 表示考虑前 \(i\) 个数 \(b_i = j\) 时的最小花费，那么 \[ f(i,j) = \min_{1\le k \le j}\left\{f(i-1,k) + |a_i - j|\right\} \] 这里需要用到 slope trick 。slope trick 是一种优化凸函数dp的方法。

考虑记 \(F_i(x) = f(i,x)\) ，定义 \(G_{i}(x) = \min_{1 \le k \le x} F_i(x)\) ，那么转移方程可以写成 \[ F_i(x)=G_{i-1}(x) + |a_i-x| \] 不难发现，\(F_i(x)\) 是关于 \(x\) 的一个下凸函数。

我们只需要找到 \(F_i(x)\) 最小值的位置即可。观察方程，可以发现我们需要快速维护 \(G_i(x)\)

怎么维护呢？由于这个函数是一个分段函数，并且每一段都是一次函数

所以我们可以维护所有分段点以及最右端的一次函数（也就是最后一段的一次函数）。

由于每一个关键点都使得斜率改变了 \(1\) ，所以相邻段如果斜率的差大于 \(1\) ，需要存两遍这个关键点。

现在考虑如何用已知的 \(F_{i-1}(x)\) 和 \(G_{i-1}(x)\) 来快速维护 \(F_i(x)\) 。

记 \(p_i\) 为使得 \(F_i(x)\) 取到最小值的 \(x\) ，注意到

显然 \(p_i\) 前的所有函数斜率单调递减，而 \(p_i\) 后的所有函数斜率单调递增。
并且在 \(p_i\) 两侧的斜率分别为正或为负。
\(F_i(x)\) 是 \(F_{i-1}(x)\) 上的叠加，叠加的就是 \(|a_i-x|\) 。
斜率为正的点是没有用的，因为我们的转移是由 \(F_{i-1}(x)\) 到 \(F_i(y)\) 的，其中 \(x \le y\)

所以当我们需要 \(F_i(y)\) 时，可以直接从 \(F_{i-1}(x)\) 推过来。

综合以上几点，我们只需要维护所有左侧斜率小于 \(0\) 的关键点即可。

现在考虑 \(p_{i-1}\) 和 \(a_i\) 的关系。

若 \(p_{i-1} \le a_i\) ，在函数叠加的时候，斜率相当于全递减了 \(1\) 。

那么我们没必要将 \(a_i\) 减小到 \(p_{i-1}\) ，此时 \(p_i=a_i\) 为当前的最优解。

于是我们只需要将 \(a_i\) 扔到关键点里就好了。
若 \(p_{i-1} > a_i\) ，此时我们需要将 \(a_i\) 提到 \(p_{i-1}\) 才能保证单调不降，因此这一块的贡献为 \(p_{i-1}-a_i\) 。

那么对于所有 \(x < a_i\) ，斜率都降低了 \(1\) ，而 \(a_i < x \le p_{i-1}\) 的斜率都增加了 \(1\) 。

此时 \(p_i\) 这个点显然导致了相邻的斜率差大于 \(1\) ，需要将这个点放两次。

然后将 \(p_{i-1}\) 扔出去（现在 \(p_{i-1}\) 不是最小点了）。当然这里可能存在多个关键点相等的情况

但是因为 \(a_{i-1}\) 改到 \(a_i\) ，和 \(a_i\) 改到 \(a_{i-1}\) 的贡献是一样的

于是我们会发现，将 \(a_i,a_{i-1}\) 改成两者较小一定是最优的。

那么我们只需要维护一个优先队列就可以维护关键点了。

时间复杂度 \(\mathcal{O}(n \log n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(1e6 + 15))

int res, a[N], b[N]; priority_queue<int> q;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n, x; cin >> n; cin >> x; a[1] = b[1] = x - 1; q.push(b[1]);
    rep(i, 2, n)
    {
        cin >> x; x -= i; q.push(b[i] = x);
        if(q.top() > x) { res += q.top() - x; q.pop(); q.push(x); }
        a[i] = q.top();
    }
    Rep(i, n - 1, 1) down(a[i], a[i + 1]);
    cout << res << '\n'; rep(i, 1, n) cout << a[i] + i << " \n"[i == n];
    return 0;
}