比赛场次 511
比赛名称 近5年noip/csp题目回顾
比赛状态 已结束比赛成绩
开始时间 2022-06-25 08:30:00
结束时间 2022-06-26 17:30:00
开放分组 全部用户
注释介绍 只有历年比赛题才最接近比赛题。
题目名称 方差
输入输出 2021variance.in/out
时间限制 1000 ms (1 s)
内存限制 512 MiB
测试点数 25 简单对比
用户 结果 时间 内存 得分

方差

★★★☆   输入文件:2021variance.in   输出文件:2021variance.out   简单对比
时间限制:1 s   内存限制:512 MiB

【题目描述】

给定长度为 $n$ 的非严格递增正整数数列 $1\leq a_1\leq a_2\leq \cdots\leq a_n$。每次可以进行的操作是:任意选择一个正整数 $1<i<n$,将 $a_i$ 变为 $a_{i-1}+a_{i+1}-a_i$。求在若干次操作之后,该数列的方差最小值是多少。请输出最小值乘以 $n^2$ 的结果。

其中方差的定义为:数列中每个数与平均值的差的平方的平均值。更形式化地说,方差的定义为 $D = \frac{1}{n}\sum_{i=1}^{n}(a_i-\overline{a})^2$,其中$\overline{a}=\frac{1}{n}\sum_{i=1}^{n}a_i$。

【输入格式】

输入的第一行包含一个正整数 $n$,保证 $n\leq 10^4$。

输入的第二行有 $n$ 个正整数,其中第 $i$ 个数字表示 $a_i$ 的值。数据保证 $1\leq a_1\leq a_2\leq \cdots \leq a_n$。

【输出格式】

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

【样例1输入】

4
1 2 4 6

【样例1输出】

52

【样例1解释】

对于$(a_1,a_2,a_3,a_4)=(1,2,4,6)$,第一次操作得到的数列有$(1,3,4,6)$,第二次操作得到的新的数列有$(1,3,5,6)$。之后无法得到新的数列。

对于$(a_1,a_2,a_3,a_4)=(1,2,4,6)$,平均值为$\frac{13}{4}$,方差为$\frac{1}{4}((1-\frac{13}{4})^2+(2-\frac{13}{4})^2+(4-\frac{13}{4})^2+(6-\frac{13}{4})^2)=\frac{59}{16}$。

对于$(a_1,a_2,a_3,a_4)=(1,3,4,6)$,平均值为$\frac{7}{2}$,方差为$\frac{1}{4}((1-\frac{7}{2})^2+(3-\frac{7}{2})^2+(4-\frac{7}{2})^2+(6-\frac{7}{2})^2)=\frac{13}{4}$。

对于$(a_1,a_2,a_3,a_4)=(1,3,5,6)$,平均值为$\frac{15}{4}$,方差为$\frac{1}{4}((1-\frac{15}{4})^2+(3-\frac{15}{4})^2+(5-\frac{15}{4})^2+(6-\frac{15}{4})^2)=\frac{59}{16}$。

【样例2、3、4】

下载

【数据范围】

对于所有的数据,保证$n\leq 10000,a_i\leq 600$。

【来源】

NOIP 2021 Task3