Oj.Nbdp.Net
初赛题库
问题
状态
排名
团队
题解
课程
Login
问题 5638 --方差
5638: 方差
警告!
题目
状态
题解
题目描述
给定长度为 $n$ 的非严格递增正整数数列 $1 \le a_1 \le a_2 \le \cdots \le 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 - \bar a)}^2$,其中 $\bar a = \frac{1}{n} \sum_{i = 1}^{n} a_i$。
输入
输入的第一行包含一个正整数 $n$,保证 $n \le {10}^4$。 输入的第二行有 $n$ 个正整数,其中第 $i$ 个数字表示 $a_i$ 的值。数据保证 $1 \le a_1 \le a_2 \le \cdots \le 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}$。 **【数据范围】** | 测试点编号 | $n \le$ | $a_i \le$ | |:-:|:-:|:-:| | $1 \sim 3$ | $4$ | $10$ | | $4 \sim 5$ | $10$ | $40$ | | $6 \sim 8$ | $15$ | $20$ | | $9 \sim 12$ | $20$ | $300$ | | $13 \sim 15$ | $50$ | $70$ | | $16 \sim 18$ | $100$ | $40$ | | $19 \sim 22$ | $400$ | $600$ | | $23 \sim 25$ | ${10}^4$ | $50$ | 对于所有的数据,保证 $1 \le n \le {10}^4$,$1 \le a_i \le 600$。
发表题解
序号
标题
作者
发表时间
费用
订购数
操作
题目信息
提交
难度
省选/NOI-
标签
点击显示
if ($pr_flag) { ?>
递交数
6
已通过
3
} ;?>
通过率
50%
时间限制
1 秒
内存限制
512 MB
来源
NOIP2021
收藏
标签云
模拟
数学与数论
动态规划
贪心
字符串
排序
枚举
数组与串
深搜
高精度
循环结构
递推
递归
二分三分
宽搜
背包
质数
线段树
分治
N进制
图论
队列
最短路
堆
树
并查集
栈
状态压缩
分支结构
几何
博弈论
生成树
顺序结构
离散化
hash表
位运算
单调队列
树状数组
KMP
字典树
二分图
数学期望
AC自动机
树链剖分
差分约束
数位动态规划
函数与过程
网络流
单调栈
前缀和