鞍山赛区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);  
    }  
}