HDU 5073 Galaxy 2014 Asia AnShan Regional Contest 规律题

推公式

#include <cstdio>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 50000+3;ll a[N], b[N];
int main() {
    int T, n, m, len;
    ll x, sum, ans;
    scanf("%d", &T);
    while(T-- > 0) {
    scanf("%d%d", &n, &m);
    len = n - m;
    a[0] = b[0] = 0;
    for (int i = 1; i <= n; ++i)
scanf("%I64d", &a[i]);
sort(a+1, a+1+n);
for (int i = 1; i <= n; ++i) {
b[i] = b[i-1]+a[i]*a[i];
a[i] = a[i-1]+a[i];
}
if (len == 0) {
puts("0.0000000000000");
} else {
ans = 7 * (ll)(1e18);
for (int i = 1; i+len-1 <= n; ++i) {
x = a[i+len-1] - a[i-1];
sum = len * (b[i+len-1] - b[i-1]) - x * x;
if (sum < ans)
ans = sum;
}
long double out = (long double)ans / len;
cout << fixed << setprecision(13) << out << endl;
}
    }
    return 0;
}