New Online Judge 主页 问题 来源/分类 竞赛&作业 状态 排名 常见问答
登录 注册

2150: 推箱子 II

内存限制：512 MB 时间限制：2 S 标准输入输出
题目类型：传统 评测方式：文本比较 上传者：
提交：4 通过：3
提交提交记录统计

题目描述

给定 n 个箱子的坐标，可能存在多个箱子处于同一坐标。
现在要求每个坐标最多一个箱子，因此需要挪动一些箱子。
每个箱子最多移动 1 次，从初始坐标 x 移动到终止坐标 y 花费 (x-y)*(x-y)。
注意，箱子的花费仅考虑初始位置和终止位置，例如初始位置为 1，终止位置为 4，则代价为 3 * 3 = 9。
请求出最小花费。

输入格式

第一行为正整数 n，1≤n≤1000000。
第二行为 n 个整数表示每个箱子的坐标 a，|a[i]|≤109。
按照坐标非递减顺序输入。

输出格式

输出最小花费。

输入样例 复制 

样例1：
7
-1 -1 3 3 3 3 4

样例2：
8
2 2 2 2 2 2 4 4

输出样例 复制 

样例1：
8

样例2：
24

数据范围与提示

来源：2022.BAPC