#2134231392. [NOIP 2021] 方差

内存限制:512 MiB 时间限制:1000 ms 输入文件:variance.in 输出文件:variance.out
题目类型:传统 评测方式:文本比较
上传者: j27eGU

题目描述

一. 题目概况

中文题目名称 方差
英文题目与子目录名
可执行文件名
输入文件名
输出文件名
每个测试点时限
测试点数目
测试点分值
附加样例文件
结果比较方式 全文比较(过滤行末空格)
题目类型 传统
运行内存上限

二. 提交源程序文件名

对于C++语言
对于C语言
对于pascal语言

3.方差

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

其中方差的定义为:数列中每个数与平均值的差的平方的平均值。更形式化地说,方差的定义为 ,其中

输入格式

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

输入的第二行有 个正整数,其中第 个数字表示 的值。数据保证

输出格式

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

样例

样例#1

输入样例#1

4
1 2 4 6

输出样例#1

52

样例#2

输入样例#2

见附件中的 variance/variance2.in

输出样例#2

见附件中的 variance/variance2.ans

样例#3

输入样例#3

见附件中的 variance/variance3.in

输出样例#3

见附件中的 variance/variance3.ans

样例#4

输入样例#4

见附件中的 variance/variance4.in

输出样例#4

见附件中的 variance/variance4.ans

数据范围与提示

【样例解释 #1】

对于 ,第一次操作得到的数列有 ,第二次操作得到的新的数列有 。之后无法得到新的数列。

对于 ,平均值为 ,方差为

对于 ,平均值为 ,方差为

对于 ,平均值为 ,方差为

【数据范围】

测试点编号

对于所有的数据,保证

原题链接:https://www.luogu.com.cn/problem/P7962