【每日一题】Problem 1832B - Maximum Sum

原题

解决思路：

类似滑动窗口的方式，窗口大小为 k 次操作，从中找到更大的结果即可

误区：

一开始的想法是每次都在前一次的基础上减去最少的，然而在样例的第五个测试点出错，因为 10+11 > 15

#include <bits/stdc++.h>

int main() {
    int t;
    std::cin >> t;
    while (t--) {
        int n, k;
        std::cin >> n >> k;
        std::vector<int> vec(n, 0);
        for (int i = 0; i < n; ++i) std::cin >> vec[i];
        std::sort(vec.begin(), vec.end());

        long long sum = 0;
        long long cutSum = 0;
        long long ans = 0;
        for (int i = 0; i < n; ++i) {
            sum += vec[i];
            if (i >= n - k) cutSum += vec[i];
        }

        for (int i = 0; i <= k; ++i) {
            ans = std::max(ans, sum - cutSum);
            cutSum = cutSum - vec[n- k + i] + vec[i * 2] + vec[i * 2 + 1];
        }

        std::cout << ans << std::endl;
    }
    return 0;
}

更好的解

采用"前缀和"的方法省略了很多代码

#include <bits/stdc++.h>

int main() {
    int t;
    std::cin >> t;
    while (t--) {
        int n, k;
        std::cin >> n >> k;
        std::vector<long long> vec(n+1, 0); // 需要 0 位置来充当"哨兵"
        for (int i = 1; i <= n; ++i) std::cin >> vec[i];
        std::sort(vec.begin(), vec.end());

        long long ans = 0;
        for (int i = 2; i <= n; ++i) vec[i] += vec[i-1];
        for (int i = 0; i <= k; ++i) {
            ans = std::max(ans, vec[n - k + i] - vec[i * 2]); // 使用"哨兵"更加方便
        }

        std::cout << ans << std::endl;
    }
    return 0;
}