Round A one 2019 – Kick Start 2019

#include<bits/stdc++.h>

using namespace std;
const int N = 100000, INF = 0x3f3f3f3f;
int T, n, p;
int a[N], sum[N + 1];

/**
 * sum[i] - sum[i - p] = a[i-p+1] + a[i-p+2] +...+ a[i]
 * p * a[i] - (sum[i] - sum[i - p])=(p-1)*a[i] - (a[i-p+1] + a[i-p+2] + ... +  a[i-1])
 * 假设p=3,i=5
 * 那么有3*a[5]- (sum[5] - sum[2])=2 * a[5] - (a[3] + a[4]) = (a[5] - a[3]) + (a[5] - a[4])
 * 即每次计算当前元素和前面p-1个元素的差的和,依次遍历取最小值,利用前缀和来优化
 * */
int main() {
    cin >> T;
    int cnt = 1;
    while (T-- > 0) {
        cin >> n >> p;
        for (int i = 1; i < n + 1; i++) {
            cin >> a[i];
        }
        sort(a + 1, a + n + 1);
        int ans = INF;
        for (int i = 1; i < n + 1; i++) {
            sum[i] = sum[i - 1] + a[i];
        }
        for (int i = p; i < n + 1; i++) {
            ans = min(ans, p * a[i] - (sum[i] - sum[i - p]));
        }
        printf("Case #%d: %d\n", cnt, ans);
        cnt++;
    }
    return 0;
}

 

0