EOJ Monthly 2019.2 (based on February Selection) F.方差

 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("*********\n")
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\n", ans);
60     return 0;
61 }