LA 7049 Galaxy 枚举

题意:

\(x\)轴上有\(n\)个质量为\(1\)的点,他们的坐标分别为\(x_i\).

质心的坐标为\(\frac{\sum{x_i}} {n}\)

转动惯量为\(\sum{d_i^2}\),其中\(d_i\)为第\(i\)个点到质心的距离.

现在你可以至多移动其中的\(k\)个点,求可能的最小的转动惯量.

分析:

首先可以任意移动其中的\(k\)个点,我们可以选择直接将他们移动到质心的位置使得转动惯量为\(0\).

所以这就相当于删去了\(k\)个点,选剩下的\(n-k\)个点.

还有一个直观的感受是选的点越集中整体的转动惯量越小,所以我们一定要选连续的\(n-k\)个点.

所以就移动长为\(n-k\)的区间,维护一个所有区间的转动惯量的最小值.

在区间移动的过程中,质心也会跟着移动.

在移动的过程中,质心远离了一些点,质心跨过了一些点(即从这些点的左边移动到了右边),质心也靠近了一些点.

所以我们可以将这些点分成左中右三个部分.

对于左边的点来说,转动惯量一直是增大的,而且增量为\((x+ \Delta x)^2-x^2\),化简为\(2x \Delta x+{ \Delta x}^2\).再进行一次求和得到\(2 \sum{x} \Delta x + cnt {\Delta x}^2\),其中\(cnt\)为远离的那些点的个数
对于中间的点,我们就直接计算转动惯量的增量即可.在质心移动的过程中每个点最多被跨过一次,所以这里的复杂度是\(O(n)\)的
对于右边的点来说,转动惯量是一直减小的,减小的量为\(x^2 - (x - \Delta x)^2\),化简为\(2x \Delta x - { \Delta x}^2\).进行求和:\(2 \sum{x} \Delta x - cnt {\Delta x}^2\),其中\(cnt\)为靠近的那些点的个数

上式中的\(\sum{x}\)可以预处理前缀和\(pre\)计算出来.

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int maxn = 50000 + 10;

int n, k;

double x[maxn];

double pre[maxn];

inline double Sum(int i, int j) {

    return pre[j] - pre[i - 1];

}

int main()

{

    //freopen("in.txt", "r", stdin);

    int T; scanf("%d",&T);

    while(T--) {

        scanf("%d%d", &n, &k);

        for(int i = 1; i <= n; i++) scanf("%lf", x + i);

        sort(x + 1, x + n + 1);

        pre[1] = x[1];

        for(int i = 2; i <= n; i++) pre[i] = pre[i - 1] + x[i];

        double sum = 0, ans;

        for(int i = 1; i <= n - k; i++) sum += x[i];

        double center = sum / (n - k);

        double inertia = 0;

        for(int i = 1; i <= n - k; i++) inertia += (x[i] - center) * (x[i] - center);

        ans = inertia;

        int border = 0;

        while(x[border + 1] <= center) border++;

        for(int s = 2; s <= k + 1; s++) {

            int t = s + n - k - 1;

            double next_center = center + (x[t] - x[s - 1]) / (n - k);

            int next_border = border;

            while(next_border < n && x[next_border + 1] <= next_center) next_border++;

            double delta = next_center - center;

            double next_inertia = inertia;

            next_inertia -= (x[s-1]-center) * (x[s-1]-center);

            next_inertia += (x[t]-center) * (x[t]-center);

            int lft = border - s + 1, rgh = t - next_border;

            double sigl = center * lft - Sum(s, border);

            double sigr = Sum(next_border + 1, t) - center * rgh;

            next_inertia += 2 * delta * sigl + lft * delta * delta;

            next_inertia -= 2 * delta * sigr - rgh * delta * delta;

            for(int i = border + 1; i <= next_border; i++)

                next_inertia += (x[i]-next_center)*(x[i]-next_center) - (x[i]-center)*(x[i]-center);

            ans = min(ans, next_inertia);

            center = next_center;

            border = next_border;

            inertia = next_inertia;

        }

        printf("%.10f\n", ans);

    }

    return 0;

}

巴特西

LA 7049 Galaxy 枚举

题意:

分析:

最新文章

热门文章