Problem 1965 --#2020. 「HNOI2017」礼物

1965: #2020. 「HNOI2017」礼物

"
Time Limit $2$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $3$ 正确数量 $3$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签

我的室友最近喜欢上了一个可爱的小女生。马上就要到她的生日了,他决定买一对情侣手环,一个留给自己,一个送给她。每个手环上各有 nnn 个装饰物,并且每个装饰物都有一定的亮度。

但是在她生日的前一天,我的室友突然发现他好像拿错了一个手环,而且已经没时间去更换它了!他只能使用一种特殊的方法,将其中一个手环中所有装饰物的亮度增加一个相同的自然数 ccc(即非负整数)。并且由于这个手环是一个圆,可以以任意的角度旋转它,但是由于上面装饰物的方向是固定的,所以手环不能翻转。需要在经过亮度改造和旋转之后,使得两个手环的差异值最小。

在将两个手环旋转且装饰物对齐了之后,从对齐的某个位置开始逆时针方向对装饰物编号 1,2,⋯,n1, 2,\cdots, n1,2,,n,其中 nnn 为每个手环的装饰物个数,第一个手环的 iii 号位置装饰物亮度为 xix_ixi,第二个手环的 iii 号位置装饰物亮度为 yiy_iyi,两个手环之间的差异值为(参见输入输出样例和样例解释):

∑i=1n(xi−yi)2 \sum_{i = 1}^n (x_i - y_i)^2 i=1n(xiyi)2

麻烦你帮他计算一下,进行调整(亮度改造和旋转),使得两个手环之间的差异值最小,这个最小值是多少呢?

输入数据的第一行有两个数 n,mn, mn,m,代表每条手环的装饰物的数量为 nnn,每个装饰物的初始亮度小于等于 mmm
接下来两行,每行各有 nnn 个数,分别代表第一条手环和第二条手环上从某个位置开始逆时针方向上各装饰物的亮度。

输出一个数,表示两个手环能产生的最小差异值。注意在将手环改造之后,装饰物的亮度可以大于 mmm

5 6
1 2 3 4 5
6 3 3 4 5
1

对于 30%30\%30% 的数据,n≤500,m≤10n\le 500, m\le 10n500,m10
对于 70%70\%70% 的数据,n≤5000n\le 5000n5000
对于 100%100\%100% 的数据,1≤n≤50000,1≤m≤100,1≤ai≤m1\le n\le 50000, 1\le m\le 100, 1\le a_i\le m1n50000,1m100,1aim

推荐代码 查看1965 所有题解 上传题解视频得图灵币

本题记录 用 户(点击查看用户) 运行号(点击购买题解) 时 间
算法最快[$208 $ms] 范晋豪@信息与计算科学142 108673 2017-07-02 16:13:22
内存最少[$0 $KB] 淡意的温柔 590281 2020-06-03 09:40:10
第一AC 范晋豪@信息与计算科学142 108673 2017-07-02 16:13:22
第一挑战 范晋豪@信息与计算科学142 108673 2017-07-02 16:13:22

赛题来源/所属竞赛 N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛