C. 构造数列

    传统题 1000ms 256MiB

构造数列

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

样例下载

题目描述

给出一个含有 nn 个元素的数列 AA,让你构造同样含有 nn 个元素的数列 BB,要求:

  • 对于 ∀ 1≤i<j≤n1 ≤ i < j ≤ n,有 Bi≤BjB_i ≤ B_j 或 Bi≥BjB_i ≥ B_j

构造完后,定义 S=∑i=1n∣Ai−Bi∣S = \sum_{i=1}^n |Ai-Bi|。

如何构造,可以使得 S 的值尽可能的小?你只需要输出可以得到的 S 的最小值。

输入格式

第一行:一个整数 nn。

接下来 nn 行:每行一个整数 AiA_i。

输出格式

一个整数,表示答案。

样例输入

7
1
3
2
4
5
3
9

样例输出

3

数据范围

100% 的数据:1≤n≤2⋅1031 ≤ n ≤ 2 · 10^3, 0≤Ai≤1090 ≤ A_i ≤ 10^9

2026-03-17

未参加
状态
已结束
规则
OI
题目
4
开始于
2026-3-17 8:30
结束于
2026-3-17 12:00
持续时间
3.5 小时
主持人
参赛人数
8