洛谷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;
}