/ Vijos / 题库 /

数据

数据

时间限制:1秒  内存限制:256M


【题目描述】

  Mr_he 出了一道信息学竞赛题,就是给 \(n\) 个数排序。输入格式是这样的:有若干组数据。每组数据的第一个是一个整数 \(n\),表示总共有 \(n\) 个数待排序;接下来 \(n\) 个整数,分别表示这 \(n\) 个待排序的数。

  例如:3 4 2 -1 4 1 2 3 4,就表示有两组数据。第一组有 3 个数 (4,2,-1),第二组有 4 个数 (1,2,3,4)。可是现在 Mr_he 做的输入数据出了一些问题。例如:2 1 9 3 2 按理说第一组数据有 2 个数 (1,9),第二组数据有 3 个数,可是 3 后面并没有出现三个数,只出现了一个数 2 而已!

  现在 Mr_he 需要对数据进行修改,改动中“一步”的含义是对文件中的某一个数 +1 或 -1,请你写个程序,计算最少需要多少步才能将数据改得合法。

【输入格式】

  第一行一个整数 \(m\),表示 Mr_he 做的输入数据包含的整数个数。第二行包含 \(m\) 个整数 \(a[i]\),每个整数的绝对值不超过 10000。

【输出格式】

  一个整数,表示把数据修改为合法的情况下,最少需要多少步。

【输入输出样例1】

 Input

4
1 9 3 2

 Output

2

【输入输出样例2】

 Input

10
4 4 3 5 0 -4 -2 -1 3 5

 Output

3

【数据限制】

  对于 \(20\%\) 的数据,\(m≤10\),\(|a[i]|≤5\)
  对于 \(60\%\) 的数据,\(m≤5000\),\(|a[i]|≤10000\)。
  对于 \(60\%\) 的数据,\(m≤100000\),\(|a[i]|≤10000\)。

【来源】

  Mr.he

信息

ID
2558
难度
9
分类
数据结构 | 单调队列队列线段树动态规划 点击显示
标签
(无)
递交数
9
已通过
1
通过率
11%
被复制
2
上传者