YZOJ P3933 [Baltic2004]sequence

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\)

  • 样例输入

  • 样例输出

  • 样例说明

所求的 \(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\) 。

 

 

Source: BZOJ 1367…