题解：蓝桥例题3260最大区间和

先发题目内容：

问题描述

小明是一名勇敢的冒险家，他在一次探险途中发现了一组神秘的宝石，这些宝石的价值都不同。但是，他发现这些宝石会随着时间的推移逐渐失去价值，因此他必须在规定的次数内对它们进行处理。

小明想要最大化这些宝石的总价值。他有两种处理方式：

1. 选出两个最小的宝石，并将它们从宝石组中删除。
2. 选出最大的宝石，并将其从宝石组中删除。

现在，给你小明手上的宝石组，请你告诉他在规定的次数内，最大化宝石的总价值是多少。

输入格式

第一行包含一个整数 tt，表示数据组数。

对于每组数据，第一行包含两个整数 nn 和 kk，表示宝石的数量和规定的处理次数。

第二行包含 nn 个整数 a1,a2,...,ana1,a2,...,an，表示每个宝石的价值。

输出格式

对于每组数据，输出一个整数，表示在规定的次数内，最大化宝石的总价值。

样例输入

6
5 1
2 5 1 10 6
5 2
2 5 1 10 6
3 1
1 2 3
6 1
15 22 12 10 13 11
6 2
15 22 12 10 13 11
5 1
999999996 999999999 999999997 999999998 999999995

样例输出

21
11
3
62
46
3999999986

样例说明

在第一个测试用例中，两个最小值是 11 和 22，去掉它们，数组为 [5，10，6][5，10，6]，和为 2121。而最大值为 1010，去掉它，则数组为 [2,5,1,6][2,5,1,6]，和为 1414。最优的操作为执行一次操作一，得到最好的答案为 2121。

在第二个测试用例中，最优的处理结果先删除两个最小值，然后再删除一个最大值。

评测数据规模

对于 100100% 的评测数据，1≤t≤10,3≤n≤2⋅105,1≤k≤99999,2k<n1≤t≤10,3≤n≤2⋅105,1≤k≤99999,2k<n。

运行限制

蓝桥提供正解的思路是前缀和配合莫队算法，前缀和还好理解，这道题用莫队算法如何处理呢？

先说什么是莫队算法：

按照题目的要求，要么进行删掉一个最大的操作，要么就是一次性删掉两个价值最小的操作，总功能操作k次。

我们可以直接把k次操作全部放给删掉价值最大的宝石，然后每次k-1，删掉价值最大的宝石的次数也是k-1，而删除两个最小的宝石则是k+1，每一次遍历得到的结果与之前得到的最优解对比，最终找出价值最大的宝石来。

下面是代码：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5+9;
int a[N];
ll prefix[N];
 
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n,k;
        cin >> n >> k;
        for(int i=1;i<=n;++i)   cin >> a[i];
 
        //先排序再构造前缀和数组
        sort(a+1,a+n+1);
        for(int i=1;i<=n;++i)   prefix[i]=prefix[i-1]+a[i];
 
        //左删除m次，那么右侧删除k-m次
        int m;  
        //mx用于存遍历m时的每组值，ans存最大值
        ll mx=0,ans=0;
        for(m=0;m<=k;++m){
            mx=prefix[n-k+m]-prefix[2*m];
            ans=max(ans,mx);
        }
        cout << ans << endl;
    }
    return 0;
}