A202 | [NOIP2021] 方差
来源NOIP提高组 / 2021
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
NOIP2021 T3
给定长度为 $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$ 的非严格递增正整数数列 $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$ 个正整数，其中第 $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$。
**【附件下载】**
[variance.zip](https://www.luogu.com.cn/fe/api/problem/downloadAttachment/cxwlyusf)
对于 $(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$。
**【附件下载】**
[variance.zip](https://www.luogu.com.cn/fe/api/problem/downloadAttachment/cxwlyusf)
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？