[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|\) 最小。

【数据范围】

\(40\%\) 的数据 \(n≤5000\)；
\(60\%\) 的数据 \(n≤300000\)；
\(100\%\) 的数据 \(n≤10^6 , 0≤a_i≤2^{31}-1\)；

Solution

Slope trick 入门题。

先将所有 \(a_i\) 对应减去 \(i\)，要求的限制从单调上升变为单调不降。那么有一个显然的 DP：设 \(f(i,j)\) 表示第 \(i\) 个位置的值 \(\le j\) 的最小代价，那么有转移：

\[f(i,j)\gets \min\{f(i-1,j)+|j-a_i|,f(i,j-1)\} \]

直接做是 \(\mathcal O(n^2)\) 的，考虑优化。

将 \(f(i,j)\) 看成分段函数 \(g_i(j)\)，容易发现这个函数是下凸的。考虑将 \(j\) 看作自变量，那么设 \(h_i(j)=|j-a_i|\)，那么转移可以看作是 \(f_{i-1}(j)\) 整体加上分段函数 \(h_i(j)=|j-a_i|\)，然后再取一个前缀 \(\min\)。

设计一种方式来表示分段函数。使用分段函数的第一段和一个可重集来表示分段函数，其中可重集中的元素 \(x\) 表示当前分段函数在 \(x\) 处斜率 \(+1\)。如 \(f(x)=|x|\) 可以表示成为 \(f(x)=-x,\{0,0\}\)。

那么本题中的转移可以看作是加上了 \(g(j)=a_i-j,\{a_i,a_i\}\)。两个分段函数相加，直接将斜率相加，拐点直接取并集即可。

使用优先队列维护这个下凸壳的所有拐点，因为转移是取 \(\min\)，因此需要关心这个分段函数中斜率为 \(0\) 的那条线段。具体做法就是分开维护两个优先队列，\(L\) 中存储在 \(0\) 线段左侧的拐点，\(R\) 中存储在 \(0\) 线段右侧的拐点，设初始斜率为 \(K\)，那么只需要维护 \(K+\text{size}(L)=0\) 即可。本题中需要用到取前缀 \(\min\) 的操作，所以只需要保留 \(L\) 即可。

对于方案的输出，可以在转移的时候记录决策点，然后倒推出方案。

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

Code

// Cirno is not baka!
#include <bits/stdc++.h>
using namespace std;
#ifdef CIRNO
#include <debug.hpp>
#else
#define Debug(...)
#endif
#define For(i, a, b) for (int i = (a); i <= (int)(b); ++i)
#define Rof(i, a, b) for (int i = (a); i >= (int)(b); --i)
#define All(x) x.begin(), x.end()
#define pii pair<int, int>
#define fi first
#define se second
#define i64 long long
#define mkp make_pair
#define int long long
#define epb emplace_back

const int _N = 1e6 + 5, mod = 1e9 + 7, inf = 1e9;
template<typename T> void Max(T &x, T y) {x = max(x, y);}
template<typename T> void Min(T &x, T y) {x = min(x, y);}

namespace BakaCirno {
    int N, A[_N], pos[_N];
    priority_queue<int> q;
    void _() {
        cin >> N;
        For(i, 1, N) cin >> A[i], A[i] -= i;
        int K = 0;
        For(i, 1, N) {
            K += -1;
            q.emplace(A[i]), q.emplace(A[i]);
            while (K + q.size() != 0) q.pop();
            pos[i] = q.top();
        }
        Rof(i, N - 1, 1) Min(pos[i], pos[i + 1]);
        int ans = 0;
        For(i, 1, N) ans += abs(A[i] - pos[i]);
        cout << ans << '\n';
        For(i, 1, N) cout << pos[i] + i << ' ';
        cout << '\n';
    }
}

void File(const string file) {
    freopen((file + ".in").c_str(), "r", stdin);
    freopen((file + ".out").c_str(), "w", stdout);
}
signed main() {
    // File("");
    cin.tie(0)->sync_with_stdio(0); int T = 1;
    // cin >> T;
    while (T--) BakaCirno::_();
}