鞍山赛区D题

好吧,我承认这道题是水题,由于我的原因导致大家没有在赛场上A出这道题,现在把代码发上来,将n^2的复杂度降到线性的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>  
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int d[50001];

int main(){
int T,n,k;
double sum;
double sum_xi_2,sum_xi,ave,tmp;
double minx;
cin>>T;
while(T--){
cin>>n>>k;
memset(d,0,sizeof(d));
sum = 0;
sum_xi_2 = 0;
sum_xi = 0;
minx = 0;
for (int i = 0; i < n; ++i){
cin>>d[i];
}
sort(d,d+n);
for(int i=0;i<n-k;i++){
sum += d[i];
sum_xi_2 += d[i]*d[i];
}
sum_xi = sum;
ave = sum/(n-k);
minx = sum_xi_2 + (n-k)*ave*ave - 2*ave*sum_xi;
for(int i=1;i<=k;i++){
sum -= d[i-1];
sum += d[n-k+i-1];
sum_xi_2 -= d[i-1]*d[i-1];
sum_xi_2 += d[n-k+i-1]*d[n-k+i-1];
sum_xi = sum;
ave = sum/(n-k);
tmp = sum_xi_2 + (n-k)*ave*ave - 2*ave*sum_xi;
if(tmp < minx)
minx = tmp;
}
printf("%.9f\n",minx);
}
}