51Nod 1098 最小方差 (数论)

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 typedef long long LL;
 7 const int MAXN = 1e4+5;
 8 const LL INF = 1e15+5;
 9 LL a[MAXN], sum[MAXN], ans[MAXN];
10 
11 int main()
12 {
13     int n, m;
14     while(cin>>n>>m)
15     {
16         for(int i=1; i<=n; i++)
17             scanf("%lld",&a[i]);
18         sort(a+1, a+1+n);
19         sum[0] = ans[0] = 0;
20         for(int i=1; i<=n; i++){
21             sum[i] = sum[i-1] + a[i];           //前缀和
22             ans[i] = ans[i-1] + a[i]*a[i];      //^2的前缀和
23         }
24         double Min = INF;
25         for(int i=m; i<=n; i++){
26             double tmp = (ans[i]-ans[i-m])-1.0*(sum[i]-sum[i-m])*(sum[i]-sum[i-m]) / m;
27             if(tmp < Min)
28                 Min = tmp;
29         }
30         printf("%lld
", (LL)Min);　　//强行转不要小数点后面，防止四舍五入
31     }
32     return 0;
33 }