YZOJ P3933 [Baltic2004]sequence
时间限制：1000MS 内存限制：65536KB
难度：\(6.0\)
-
题目描述
给定一个序列 \(t_1,t_2,\cdots,t_n\)，求一个递增序列 \(z_1<z_2<\cdots<z_n\)，使得 \(R=\sum\limits_{i=1}^{n}{\left|t_i-z_i\right|}\) 的值最小。
本题中，我们只需要求出这个最小的 \(R\) 值。
-
输入格式
第一行为一个正整数 \(n\)
第二行到第 \(n+1\) 行，每行一个整数，第 \(k+1\) 行为 \(t_k\)
-
输出格式
一个整数 \(R\)
-
样例输入
|
1 2 3 4 5 6 7 8 |
7 9 4 8 20 14 15 18 |
-
样例输出
|
1 |
13 |
-
样例说明
所求的 \(z\) 序列为 \(6,7,8,13,14,15,18\)，\(R=13\)
-
数据规模与约定
对于 \(100\%\) 的数据，\(1 \leq n \leq 10^6\)，\(1 \leq t_i \leq 2\times 10^9\) 。