题目描述
给定长度为 nn 的非严格递增正整数数列 1≤a1≤a2≤⋯≤an1≤a1≤a2≤⋯≤an。每次可以进行的操作是:任意选择一个正整数 1<i<n1<i<n,将 aiai 变为 ai−1+ai+1−aiai−1+ai+1−ai。求在若干次操作之后,该数列的方差最小值是多少。请输出最小值乘以 n2n2 的结果。
其中方差的定义为:数列中每个数与平均值的差的平方的平均值。更形式化地说,方差的定义为 D=1n∑i=1n(ai−a¯)2D=n1∑i=1n(ai−a¯)2,其中 a¯=1n∑i=1naia¯=n1∑i=1nai。
输入格式
输入的第一行包含一个正整数 nn,保证 n≤104n≤104。
输入的第二行有 nn 个正整数,其中第 ii 个数字表示 aiai 的值。数据保证 1≤a1≤a2≤⋯≤an1≤a1≤a2≤⋯≤an。
输出格式
输出仅一行,包含一个非负整数,表示你所求的方差的最小值的 n2n2 倍。
输入输出样例
输入#1
4 1 2 4 6
输出#1
52
说明/提示
【样例解释 #1】
对于 (a1,a2,a3,a4)=(1,2,4,6)(a1,a2,a3,a4)=(1,2,4,6),第一次操作得到的数列有 (1,3,4,6)(1,3,4,6),第二次操作得到的新的数列有 (1,3,5,6)(1,3,5,6)。之后无法得到新的数列。
对于 (a1,a2,a3,a4)=(1,2,4,6)(a1,a2,a3,a4)=(1,2,4,6),平均值为 134413,方差为 14((1−134)2+(2−134)2+(4−134)2+(6−134)2)=591641((1−413)2+(2−413)2+(4−413)2+(6−413)2)=1659。
对于 (a1,a2,a3,a4)=(1,3,4,6)(a1,a2,a3,a4)=(1,3,4,6),平均值为 7227,方差为 14((1−72)2+(3−72)2+(4−72)2+(6−72)2)=13441((1−27)2+(3−27)2+(4−27)2+(6−27)2)=413。
对于 (a1,a2,a3,a4)=(1,3,5,6)(a1,a2,a3,a4)=(1,3,5,6),平均值为 154415,方差为 14((1−154)2+(3−154)2+(5−154)2+(6−154)2)=591641((1−415)2+(3−415)2+(5−415)2+(6−415)2)=1659。
【数据范围】
测试点编号 | n≤n≤ | ai≤ai≤ |
---|---|---|
1∼31∼3 | 44 | 1010 |
4∼54∼5 | 1010 | 4040 |
6∼86∼8 | 1515 | 2020 |
9∼129∼12 | 2020 | 300300 |
13∼1513∼15 | 5050 | 7070 |
16∼1816∼18 | 100100 | 4040 |
19∼2219∼22 | 400400 | 600600 |
23∼2523∼25 | 104104 | 5050 |
对于所有的数据,保证 1≤n≤1041≤n≤104,1≤ai≤6001≤ai≤600。
-
扫码下载安卓APP
-
微信扫一扫关注我们
微信扫一扫打开小程序
手Q扫一扫打开小程序
-
返回顶部
发表评论