蓝桥杯省赛无忧 编程11 最大数组和

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    int t;
    cin >> t;
    while(t--){
        int n, k;
        cin >> n >> k;
        vector<ll> a(n), sum(n + 1, 0);
        for(int i = 0;i < n;i++) cin >> a[i];
        sort(a.begin(), a.end());
        for(int i = 1;i <= n;i++) sum[i] = sum[i - 1] + a[i - 1];
        ll ans = 0;
        int pos = 0;
        while(k >= 0){
            ans = max(ans, sum[n - k] - sum[pos]);
            pos += 2;
            k--;
        }
        cout << ans << "\n";
    }
    return 0;
}

代码逻辑分析：

1. 读取测试用例的数量t。
2. 对于每个测试用例：
   • 读取宝石的数量n和可执行的操作次数k。
   • 声明一个长整型向量a来存储宝石的价值，并且初始化一个长整型向量sum，其元素数量为宝石数量加一，用于存储累加和。
   • 读取n个宝石的价值，并将它们存储在向量a中。
   • 对向量a进行排序。
   • 通过累加和向量sum来计算从第一个宝石到当前宝石的总价值。
   • 初始化答案ans为0，设置一个指针pos指向宝石数组的开始。
   • 当剩余操作次数k不小于0时，尝试找出最大化的宝石总价值：
     • ans更新为当前剩余宝石总价值（sum[n - k]）减去当前位置到开始位置的宝石总价值（sum[pos]）的最大值。
     • 指针pos每次增加2，因为每次操作会移除两个最小的宝石。
     • 操作次数k每次减少1。
   • 输出当前测试用例的最大化总价值ans。

核心算法的思路是，每次循环都计算出在删除掉pos和pos + 1索引处的宝石之后（代表每次操作删除两个最小的宝石），以及删除掉最后k个宝石（代表每次操作删除最大的宝石）后剩余宝石的总价值。每次迭代都尝试更新ans，以保证获取到最大的价值。

这段代码巧妙地结合了排序、前缀和和贪心算法的思想，快速求解出在给定操作次数内能达到的最大宝石总价值。