【ACWing】2725. 数字序列

题目地址：

https://www.acwing.com/problem/content/2727/

给定一个整数序列$a_1,a_2,\cdot \cdot \cdot ,a_n$。请你求出一个递增序列$b_1<b_2<\cdot \cdot \cdot <b_n$，使得序列$a_i$和$b_i$的各项之差的绝对值之和$s=|a_1-b_1|+|a_2-b_2|+\cdot \cdot \cdot +|a_n-b_n|$最小。

输入格式：
第一行包含整数$n$。
第二行包含$n$个整数$a_1,a_2,\cdot \cdot \cdot ,a_n$。

输出格式：
第一行输出绝对值之和的最小值。
第二行输出$b_1,b_2,\cdot \cdot \cdot ,b_n$。
输出任意合理方案即可。

数据范围：
$1\le n\le 10^6$
$0\le a_i\le 2\times 10^9$

考虑序列 { a i ′ } = { a i − i } \{a'_i\}=\{a_i-i\} {ai′​}={ai​−i}，则$a_i^{\prime }$是非严格递增序列，如果我们能对 { a i ′ } \{a'_i\} {ai′​}求解出 { b i ′ } \{b'_i\} {bi′​}，则各项之差的绝对值之和和不变换的情况是一样的，最后只需要将$b_i^{\prime }$加上$i$即可还原成$b_i$。不妨仍然用$a$来表示$a^{\prime }$。

考虑这个新问题。求$s$最小值可以参考https://blog.csdn.net/qq_46105170/article/details/126434434。关于如何求$b$，我们只需要将其构造出来即可。每次循环结束之前的时候，我们直接将$b[i]$赋值为堆顶，最后逆序遍历，让$b_i$取 min ⁡ { b i , b i + 1 } \min\{b_i,b_{i+1}\} min{bi​,bi+1​}就行了。

可以用数学归纳法。显然算法对$n=1$的情形正确。假设算法对$\le n-1$的情形都正确，考虑$n$的情形。假设对于$n-1$的时候，解为$b_1,...,b_{n-1}$。此时如果$a_i\ge b_{n-1}$，由于$b_{n-1}$是上一轮结束后的堆顶，所以当前轮循环$b_i$将会取$a_i$，这个确实是最优解，因为$s$没有变大；如果$a_i<b_{n-1}$，那么其实就是看循环结束之前，堆中除了$b_{n-1}$之外最大的是谁。如果是$x\ge a_i$，则将$b_{n-1}$下降到$x$，将$b_i$取为$x$，总代价增加值符合；如果$x<a_i$，则$b_i$是取$x$产生的新代价为$a_i-x$，也符合（同时可以归纳假设其余调整不会产生新的代价）。

注意不能用STL里的堆，而要手写一个，否则会超时。代码如下：

#include 
using namespace std;

const int N = 1e6 + 10;
int n;
long a[N];
long h[N];
int sz;

void sift_up(int k) {
  while (k > 1 && h[k] > h[k >> 1]) {
    swap(h[k], h[k >> 1]);
    k >>= 1;
  }
}

void sift_down(int k) {
  while (k * 2 <= sz) {
    int t = k;
    if (h[k * 2] > h[t]) t = k * 2;
    if (k * 2 + 1 <= sz && h[k * 2 + 1] > h[t]) t = k * 2 + 1;
    if (t == k) return;
    swap(h[k], h[t]);
    k = t;
  }
}

void push(long x) {
  h[++sz] = x;
  sift_up(sz);
}

void pop() {
  h[1] = h[sz--];
  sift_down(1);
}

#define top() h[1]

int main() {
  scanf("%d", &n);
  long res = 0;
  for (int i = 1; i <= n; i++) {
    long x;
    scanf("%ld", &x);
    x -= i;
    push(x);
    if (top() > x) {
      res += top() - x;
      pop();
      push(x);
    }
    a[i] = top();
  }

  printf("%ld\n", res);
  for (int i = n - 1; i; i--) a[i] = min(a[i], a[i + 1]);
  for (int i = 1; i <= n; i++) printf("%ld ", a[i] + i);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

时间复杂度$O(n\log n)$，空间$O(n)$。