3678.方差 – Xhesica's blog

3678.方差

2020-7-19 11:35

1,002

未分类

71 字

几秒读完

链接：Miku

题目非常”简单“

乍一看题，和和积积真讨厌

但是为什么要乘m^2呢

这时候我们拿起来了?，乘乘画画，一个答案呼之欲出

（看一下代码就懂了）

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
long long q[1000001],qq[1000001];
int n,m;
int k;
long long now;
long long ans;
long long sum,mi;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%d",&k);
        q[i]=k;
        qq[i]=k*k;
    }
    sort(q+1,q+n+1);
    sort(qq+1,qq+n+1);
    for(int i=1;i<=m;++i){
        sum+=q[i];
        mi+=qq[i];
    }
    now=ans=m*mi-sum*sum;
    for(int i=m+1;i<=n;++i){
        sum=sum+q[i]-q[i-m];
        mi=mi+qq[i]-qq[i-m];
        now=m*mi-sum*sum;
        ans=min(ans,now);
    }
    cout<<ans;
    return 0;
}