【CodeForces】CF13C Sequence（配数学证明）

题目地址：

https://www.luogu.com.cn/problem/CF13C

题面翻译：
给定一个序列，每次操作可以把某个数加$1$或者减$1$。要求把序列变成非降数列。而且要求修改后的数列只能出现修改前的数。

题目描述：
Little Petya likes to play very much. And most of all he likes to play the following game:

He is given a sequence of $N$ integer numbers. At each step it is allowed to increase the value of any number by $1$ or to decrease it by $1$ . The goal of the game is to make the sequence non-decreasing with the smallest number of steps. Petya is not good at math, so he asks for your help.

The sequence $a$ is called non-decreasing if $a_1\le a_2\le ...\le a_N$ holds, where $N$ is the length of the sequence.

输入格式：
The first line of the input contains single integer $N$ ( $1\le N\le 5000$ ) — the length of the initial sequence. The following $N$ lines contain one integer each — elements of the sequence. These numbers do not exceed $10^9$ by absolute value.

输出格式：
Output one integer — minimum number of steps required to achieve the goal.

求最小操作次数可以参考https://blog.csdn.net/qq_46105170/article/details/126434434
。这题里要求最后得到的序列只能含修改前的数，所以这里只需要证明存在一个最优解恰好只含修改前的数即可。

设修改前的数集合为$A$，修改后得到的序列为$b$，且操作次数最少，设$a_i$从小到大排好序之后所得的序列为$a_i^{\prime }$。如果$b_i\notin A$，假设$a_j^{\prime }<b_i<a_{j+1}^{\prime }$（$b_i$必然在某两个$a^{\prime }$之间的，否则只能让操作次数变得更大），进一步假设$i$是使得上面不等式成立的最小下标，设$a_j^{\prime }<b_i\le b_{i+1}\le ...\le b_{i+c}<a_{j+1}^{\prime }<b_{i+c+1}$。考虑$a_i,a_{i+1},...,a_{i+c}$，设这些数大于等于$a_{j+1}^{\prime }$的数有$x$个，小于等于$a_j^{\prime }$的数有$y$个，如果$x>y$，那么将$b_i,b_{i+1},...,b_{i+c}$整体上移可以得到更优解，矛盾；同理如果$x<y$也矛盾。当$x=y$的时候，可以直接将$b_i,b_{i+1},...,b_{i+c}$整体下移使得$b_i$移动到$a_j^{\prime }$处，仍然是最优解。所以经过有限步就可以使得$\forall i,b_i\in A$。

代码如下：

#include 
#include 
using namespace std;
using LL = long long;

const int N = 5010;
int n, a[N];

LL solve() {
  LL res = 0;
  priority_queue<int> heap;
  for (int i = 1; i <= n; i++) {
    heap.push(a[i]);
    if (a[i] < heap.top()) {
      res += heap.top() - a[i];
      heap.pop();
      heap.push(a[i]);
    }
  }
  return res;
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  printf("%lld\n", solve());
}
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

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