程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 5073 Galaxy

HDU 5073 Galaxy

編輯：C++入門知識

HDU 5073 Galaxy

題意：

數軸上有n個點每個點重量1 可以移動其中k個到任何位置使得題中式子值最小 di表示第i個點距離現在n個點的重心的距離

思路：

式子中wi可以去掉因為都是1 則式子變成I=min(sum(di*di))

考慮移動的k個點應該直接把它們移到重心這樣di為0

很容易想到我們將所有點排序後應該從兩邊往中間拿這樣移動k個點剩下一些連續的點因此可以枚舉剩下的連續區間

此時我們把I變形 I = min(sum(di*di))

= min(sum((li-mi)*(li-mi))) （li即i點的位置 mi為這幾個點的重心）

= min( sum(li*li) - 2*mi*sum(li) + mi*mi*(n-k) )

這樣我們可以用前綴和來維護答案結合上面的枚舉復雜度也就是O(n)

代碼：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
#define M 50010
#define mod 1000000007

int T, n, k;
double s[M], s2[M];
double ans;

int main() {
    int i, j;
    double tmp, mid;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &k);
        for (i = 1; i <= n; i++)
            scanf("%lf", &s[i]);
        ans = 0;
        if (n != k) {
            sort(s + 1, s + n + 1);
            for (i = 1; i <= n; i++)
                s2[i] = s[i] * s[i];
            double sum1 = 0, sum2 = 0;
            for (i = 1; i <= n - k; i++) {
                sum1 += s[i];
                sum2 += s2[i];
            }
            mid = sum1 / (n - k);
            ans = sum2 - 2.0 * mid * sum1 + mid * mid * (n - k);
            for (i = 2, j = n - k + 1; j <= n; i++, j++) {
                sum1 -= s[i - 1];
                sum1 += s[j];
                sum2 -= s2[i - 1];
                sum2 += s2[j];
                mid = sum1 / (n - k);
                tmp = sum2 - 2.0 * mid * sum1 + mid * mid * (n - k);
                if (tmp < ans)
                    ans = tmp;
            }
        }
        printf("%.10f\n", ans);
    }
    return 0;
}