真就普及-是吧

原题链接：3.方差

子曲锦程

2024-06-29 14:52:12

发布于：上海

60阅读

0回复

0点赞

看题，好打开python（
递归，启动！

n = int(input())
num_lst = [int(i) for i in input().split(" ")]
all = [num_lst.copy()]
def run(lst,i):
    global all
    num = lst[i+1]+lst[i-1]-lst[i]
    if lst[i-1] <= num and lst[i+1] >= num:
        lst[i] = num
        if lst.copy() not in all:
            all.append(lst.copy())
            for i in range(1,n-1):
                run(lst.copy(),i)
for i in range(1,n-1):
    run(num_lst.copy(),i)
res_lst = []
for num in all:
    average = sum(num)/n
    res = sum([(i-average)**2 for i in num])*n
    res_lst.append(res)
print(int(min(res_lst)))

运行！RE！
？
打开idle
非常好超出最大递归深度！
写nm！

有帮助，赞一个

去预览

0/2000

全部评论 5

北辞
666

2024-07-04 来自广东
0

李总

[NOIP2021] 方差

题目描述

给定长度为 $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

样例输入 #1

4
1 2 4 6

样例输出 #1

样例 #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】

对于 $(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$