解决思路：
类似滑动窗口的方式，窗口大小为 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;
}