真就普及-是吧

原题链接：3.方差
userId_undefined
子曲锦程

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！

userId_undefined
去预览
0/2000

全部评论 5

  • userId_undefined
    北辞
    出道萌新荣耀黄金

    666

    2024-07-04 来自 广东

    0
  • userId_undefined
    LZM
    出道萌新荣耀黄金

    [NOIP2021] 方差

    题目描述

    给定长度为 nn 的非严格递增正整数数列 1≤a1≤a2≤⋯≤an1 \le a_1 \le a_2 \le \cdots \le a_n。每次可以进行的操作是：任意选择一个正整数 1<i<n1 < i < n，将 aia_i 变为 ai−1+ai+1−aia_{i - 1} + a_{i + 1} - a_i。求在若干次操作之后，该数列的方差最小值是多少。请输出最小值乘以 n2n^2 的结果。

    其中方差的定义为：数列中每个数与平均值的差的平方的平均值。更形式化地说，方差的定义为 D=1n∑i=1n(ai−aˉ)2D = \frac{1}{n} \sum_{i = 1}^{n} {(a_i - \bar a)}^2，其中 aˉ=1n∑i=1nai\bar a = \frac{1}{n} \sum_{i = 1}^{n} a_i。

    输入格式

    输入的第一行包含一个正整数 nn，保证 n≤104n \le {10}^4。

    输入的第二行有 nn 个正整数，其中第 ii 个数字表示 aia_i 的值。数据保证 1≤a1≤a2≤⋯≤an1 \le a_1 \le a_2 \le \cdots \le a_n。

    输出格式

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

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

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

    对于 (a1,a2,a3,a4)=(1,2,4,6)(a_1, a_2, a_3, a_4) = (1, 2, 4, 6)，平均值为 134\frac{13}{4}，方差为 14((1−134)2+(2−134)2+(4−134)2+(6−134)2)=5916\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}。

    对于 (a1,a2,a3,a4)=(1,3,4,6)(a_1, a_2, a_3, a_4) = (1, 3, 4, 6)，平均值为 72\frac{7}{2}，方差为 14((1−72)2+(3−72)2+(4−72)2+(6−72)2)=134\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}。

    对于 (a1,a2,a3,a4)=(1,3,5,6)(a_1, a_2, a_3, a_4) = (1, 3, 5, 6)，平均值为 154\frac{15}{4}，方差为 14((1−154)2+(3−154)2+(5−154)2+(6−154)2)=5916\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≤n \le ai≤a_i \le
    1∼31 \sim 3 44 1010
    4∼54 \sim 5 1010 4040
    6∼86 \sim 8 1515 2020
    9∼129 \sim 12 2020 300300
    13∼1513 \sim 15 5050 7070
    16∼1816 \sim 18 100100 4040
    19∼2219 \sim 22 400400 600600
    23∼2523 \sim 25 104{10}^4 5050

    对于所有的数据，保证 1≤n≤1041 \le n \le {10}^4，$1 \le a_i \l

    2024-07-04 来自 四川

    0
  • userId_undefined
    cjdst
    小有名气尊贵铂金CSP-S一等奖

    普及-水题你都做不对？（不是

    2024-07-04 来自 广东

    0
  • userId_undefined
    leo120306
    出道萌新秩序白银时空双修者时间刺客空间掌握者

    此题实际难度为紫：）

    2024-07-01 来自 上海

    0
  • userId_undefined
    。

    6

    2024-06-29 来自 广东

    0

热门讨论