题目

Description

Good news for us: to release the financial pressure, the government started selling galaxies and we can buy them from now on! The first one who bought a galaxy was Tianming Yun and he gave it to Xin Cheng as a present.

To be fashionable, DRD also bought himself a galaxy. He named it Rho Galaxy. There are n stars in Rho Galaxy, and they have the same weight, namely one unit weight, and a negligible volume. They initially lie in a line rotating around their center of mass.

Everything runs well except one thing. DRD thinks that the galaxy rotates too slow. As we know, to increase the angular speed with the same angular momentum, we have to decrease the moment of inertia.

The moment of inertia I of a set of n stars can be calculated with the formula

where w i is the weight of star i, d i is the distance form star i to the mass of center.

As DRD’s friend, ATM, who bought M78 Galaxy, wants to help him. ATM creates some black holes and white holes so that he can transport stars in a negligible time. After transportation, the n stars will also rotate around their new center of mass. Due to financial pressure, ATM can only transport at most k stars. Since volumes of the stars are negligible, two or more stars can be transported to the same position.

Now, you are supposed to calculate the minimum moment of inertia after transportation.

Input

The first line contains an integer T (T ≤ 10), denoting the number of the test cases.

For each test case, the first line contains two integers, n(1 ≤ n ≤ 50000) and k(0 ≤ k ≤ n), as mentioned above. The next line contains n integers representing the positions of the stars. The absolute values of positions will be no more than 50000.

Output

For each test case, output one real number in one line representing the minimum moment of inertia. Your answer will be considered correct if and only if its absolute or relative error is less than 1e-9.

Sample Input

2
3 2
-1 0 1
4 2
-2 -1 1 2

Sample Output

0
0.5

题解

给一些数,删去一些数,使剩下的数的方差最小

方差的意义是一串数的离散程度
因此应该尽可能选取 “近” 的数

那么首先要做的第一件事就是排序
这样只需要找到连续的串中最大的就行

所以可以再 O(n) 的时间里扫描所有的串

由于串的长度是确定的,因此每次都是减去一个数再加上一个数
因此可以在 O(1) 的时间里算出所有数的和 sum 和平方的和 sums

我们要算的是方差,方差是 所有数与平均数的平方的和除以数目

也即 average = sum/(n-k) ans = {(a[i] - average)*(a[i] - average)}/(n-k)

展开化简可得 ans = (n - k)*average*average + sums - 2 * average*sum

这样可以再 O(1) 的时间算出来当前串的方差

能优化到这一步一般题应该没问题了,但是这个题还存在 溢出 的情况, sums 最大是非常大的,如果用 double 存,最高位和最低位错的会比较多
只能继续转换公式,尽可能用 long long 存

再把上面的式子展开化简可得 ans = sums - sum*sum/(n-k)
有一点技巧就是 在这里可以用 long long 保存
ans = (n - k)*sums - sum*sum
比较和保存这个值,由于 n-k 是常数,并不会对结果造成影响,最后输出的时候再除以 n-k 即可

注意各种细节的处理,因为 for 的循环条件坑了好久……

代码

/*
By:OhYee
Github:OhYee
Blog:http://www.oyohyee.com/
Email:oyohyee@oyohyee.com

かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <list>
#include <queue>
#include <stack>
#include <string>
#include <vector>
#include <bitset>
#include <functional>

using namespace std;

const int INF = 0x7FFFFFFF;
const double eps = 1e-10;

const int maxn = 50005;

int n,k;
long long a[maxn];

void Do() {
    cin >> n >> k;
    for(int i = 0;i < n;i++)
        cin >> a[i];
    if(n - k > 1) {
        sort(a,a + n);
        long long Min = -1;
        long long sum = 0;
        long long sums = 0;
        for(int i = 0;i < n - k;i++) {
            sum += a[i];
            sums += a[i] * a[i];
        }

        for(int i = 0;i <= k;i++) {
            if(i) {
                sum -= a[i - 1];
                sum += a[n - k + i - 1];
                sums -= a[i - 1] * a[i - 1];
                sums += a[n - k + i - 1] * a[n - k + i - 1];
            }
            //double average = sum / (double)(n - k);

            //double ans = (double)(n - k)*average*average + sums - 2 * average*sum;

            long long ans = (n - k)*sums - sum*sum;

            if(Min == -1)
                Min = ans;
            else
                Min = min(Min,ans);
        }
        if(Min == -1)
            Min = 0;
        cout << fixed << setprecision(11) << (double)Min / (double)(n - k) << endl;
    } else {
        cout << 0 << endl;
    }
}

int main() {
    cin.tie(0);
    cin.sync_with_stdio(false);

    int T;
    cin >> T;
    while(T--)
        Do();

    return 0;
}