题目链接：
https://acm.ecnu.edu.cn/contest/140/problem/F/
题目：
思路：
因为方差是用来评估数据的离散程度的，因此最优的m个数一定是排序后连续的，所以我们可以先排序然后对每m个连续的数取个min。
代码实现如下：
1 #include <set> 2 #include <map> 3 #include <deque> 4 #include <queue> 5 #include <stack> 6 #include <cmath> 7 #include <ctime> 8 #include <bitset> 9 #include <cstdio> 10 #include <string> 11 #include <vector> 12 #include <cstdlib> 13 #include <cstring> 14 #include <iostream> 15 #include <algorithm> 16 using namespace std; 17 18 typedef long long LL; 19 typedef pair<LL, LL> pLL; 20 typedef pair<LL, int> pLi; 21 typedef pair<int, LL> pil;; 22 typedef pair<int, int> pii; 23 typedef unsigned long long uLL; 24 25 #define lson rt<<1 26 #define rson rt<<1|1 27 #define lowbit(x) x&(-x) 28 #define name2str(name) (#name) 29 #define bug printf("********* ") 30 #define debug(x) cout<<#x"=["<<x<<"]" <<endl 31 #define FIN freopen("D://code//in.txt","r",stdin) 32 #define IO ios::sync_with_stdio(false),cin.tie(0) 33 34 const double eps = 1e-8; 35 const int mod = 1000000007; 36 const int maxn = 1e6 + 7; 37 const double pi = acos(-1); 38 const int inf = 0x3f3f3f3f; 39 const LL INF = 0x3f3f3f3f3f3f3f3fLL; 40 41 int n, m; 42 int a[maxn]; 43 LL sum1[maxn], sum2[maxn]; 44 45 int main(){ 46 scanf("%d%d", &n, &m); 47 for(int i = 1; i <= n; i++) { 48 scanf("%d", &a[i]); 49 } 50 sort(a + 1, a + n + 1); 51 for(int i = 1; i <= n; i++) { 52 sum1[i] = sum1[i-1] + a[i]; 53 sum2[i] = sum2[i-1] + a[i] * a[i]; 54 } 55 LL ans = INF; 56 for(int i = 1; i <= n - m + 1; i++) { 57 ans = min(ans, m * (sum2[i+m-1] - sum2[i-1]) - (sum1[i+m-1] - sum1[i-1]) * (sum1[i+m-1] - sum1[i-1])); 58 } 59 printf("%lld ", ans); 60 return 0; 61 }