当前位置：首页 > news >正文

题解：洛谷 P7962 [NOIP2021] 方差

news 2026/4/28 12:46:08

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

洛谷：P7962 [NOIP2021] 方差 - 洛谷

【题目描述】

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

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

【输入】

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

输入的第二行有n nn个正整数，其中第i ii个数字表示a i a_iai的值。数据保证1 ≤ a 1 ≤ a 2 ≤ ⋯ ≤ a n 1 \le a_1 \le a_2 \le \cdots \le a_n1≤a1≤a2≤⋯≤an。

【输出】

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

【输入样例】

4 1 2 4 6

【输出样例】

【解题思路】

【算法标签】

#省选# #线性DP-一维#

【代码详解】

// 32分版本#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=2005;intn;// 序列长度inta[N];// 原始序列intda[N];// 差分序列signedmain(){cin>>n;// 输入序列长度for(inti=1;i<=n;i++)// 输入原始序列{cin>>a[i];}// 计算差分序列：da[i] = a[i+1] - a[i]for(inti=1;i<n;i++){da[i]=a[i+1]-a[i];}// 对差分序列进行排序，为全排列做准备sort(da+1,da+n);intans=1e9;// 初始化答案为无穷大// 枚举差分序列的所有排列do{ints1=0;// 用于计算 Σfᵢ²ints2=0;// 用于计算 Σfᵢintfa=0;// 累积的f值// 根据当前排列计算f值for(inti=1;i<n;i++){fa+=da[i];// 计算当前的f值s1+=fa*fa;// 累加fᵢ²s2+=fa;// 累加fᵢ}// 计算当前排列的代价：n * Σfᵢ² - (Σfᵢ)²ans=min(ans,n*s1-s2*s2);}while(next_permutation(da+1,da+n));// 生成下一个排列cout<<ans<<endl;// 输出最小代价return0;// 程序正常结束}

// 100分版本#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=10005,M=500005,INF=1e18;intn;// 序列长度inta[N];// 原始序列intd[N];// 差分序列ints[N];// 差分序列的前缀和intans=1e18;// 最终答案intdp[2][M];// 滚动数组，用于动态规划signedmain(){// 输入处理cin>>n;// 输入序列长度for(inti=1;i<=n;i++)// 输入原始序列{cin>>a[i];}// 计算差分序列：d[i] = a[i+1] - a[i]for(inti=1;i<n;i++){d[i]=a[i+1]-a[i];}// 对差分序列进行排序sort(d+1,d+n);// 计算差分序列的前缀和for(inti=1;i<n;i++){s[i]=s[i-1]+d[i];}// 动态规划初始化dp[0][0]=0;// 初始状态：没有元素时，总和为0// 动态规划主循环for(inti=0;i<n-1;i++)// 处理差分序列的前i+1个元素{// 初始化下一行的dp数组为无穷大for(intj=0;j<=s[i+1]*(i+1);j++){dp[1][j]=INF;}// 状态转移for(intj=0;j<=s[i]*i;j++)// 枚举当前可能的总和{if(dp[0][j]<INF)// 如果当前状态可达{// 转移1: 将d[i+1]加入当前集合dp[1][j+s[i+1]]=min(dp[1][j+s[i+1]],dp[0][j]+s[i+1]*s[i+1]);// 转移2: 以某种方式处理d[i+1] (需要推导具体含义)dp[1][j+(i+1)*d[i+1]]=min(dp[1][j+(i+1)*d[i+1]],dp[0][j]+(i+1)*d[i+1]*d[i+1]+2*j*d[i+1]);}}// 滚动数组：将下一行的值复制到当前行for(intj=0;j<=s[i+1]*(i+1);j++){dp[0][j]=dp[1][j];}}// 在最终状态中寻找最优解for(intS=0;S<=s[n-1]*(n-1);S++)// 枚举所有可能的总和{if(dp[0][S]==INF)// 如果状态不可达，跳过{continue;}// 计算最终代价：n * dp[0][S] - S * Sans=min(ans,n*dp[0][S]-S*S);}cout<<ans<<endl;// 输出最小代价return0;// 程序正常结束}