小码农

趣味编程-面向每个人的创意编程

题目描述

给定长度为 n 的非严格递增正整数数列 1≤a1≤a2≤⋯≤an。每次可以进行的操作是:任意选择一个正整数 1<i<n,将 ai 变为 ai−1+ai+1−ai。求在若干次操作之后,该数列的方差最小值是多少。请输出最小值乘以 n2 的结果。

其中方差的定义为:数列中每个数与平均值的差的平方的平均值。更形式化地说,方差的定义为 D=1n∑i=1n(ai−a¯)2,其中 a¯=1n∑i=1nai

输入格式

输入的第一行包含一个正整数 n,保证 n≤104

输入的第二行有 n 个正整数,其中第 i 个数字表示 ai 的值。数据保证 1≤a1≤a2≤⋯≤an

输出格式

输出仅一行,包含一个非负整数,表示你所求的方差的最小值的 n2 倍。

输入输出样例

输入#1

4
1 2 4 6

 

输出#1

52

 

说明/提示

【样例解释 #1】

对于 (a1,a2,a3,a4)=(1,2,4,6),第一次操作得到的数列有 (1,3,4,6),第二次操作得到的新的数列有 (1,3,5,6)。之后无法得到新的数列。

对于 (a1,a2,a3,a4)=(1,2,4,6),平均值为 134,方差为 14((1−134)2+(2−134)2+(4−134)2+(6−134)2)=5916

对于 (a1,a2,a3,a4)=(1,3,4,6),平均值为 72,方差为 14((1−72)2+(3−72)2+(4−72)2+(6−72)2)=134

对于 (a1,a2,a3,a4)=(1,3,5,6),平均值为 154,方差为 14((1−154)2+(3−154)2+(5−154)2+(6−154)2)=5916

【数据范围】

测试点编号 n≤ ai≤
1∼3 4 10
4∼5 10 40
6∼8 15 20
9∼12 20 300
13∼15 50 70
16∼18 100 40
19∼22 400 600
23∼25 104 50

对于所有的数据,保证 1≤n≤1041≤ai≤600

发表评论