蓝桥 3260. 最大数组和 ​

题目 ​

1.最大数组和 - 蓝桥云课

问题描述 ​

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

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

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

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

输入格式 ​

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

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

第二行包含 $n$个整数 $a_1,a_2,...,a_n$，表示每个宝石的价值。

输出格式 ​

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

样例输入 ​

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

样例说明 ​

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

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

评测数据规模 ​

对于 100% 的评测数据，$1\le t\le 10,3\le n\le 2\cdot {10}^5,1\le k\le 99999,2k<n$。

题解 ​

一种错误思路——贪心 ​

首先，很容易可以想到一种贪心的做法，在每一次操作中比较删除的两个最小值之和与一个最大值的大小，删除小的一方即可。但是我们发现，后面的操作可以删除的“最小”和“最大”，取决于之前的动作：如果删除了最大值，列表的最大值就会更新；删除了两个最小值，列表的最小值也会更新。这会带来什么影响呢？就像这个例子：

#input
6 2
15 22 12 10 13 11
#output
46

如果采用我们的贪心思路，可以发现：第一次删除两个最小值10和11，第二次删除一个最大值22，得到的结果仅仅只有40。而按照最优的结果，我们可以发现，该方案是删除了22和15两个最大值。第一次尝试，就此失败了！

新的发现——前缀和 ​

我们可以从这个方案中看出，【先删除最小两个，再删除最大的】和【先删除最大的，再删除最小两个】的结果是一样的，因此我们可以得出一个重要的结论：最终结果与操作顺序无关，仅仅与删除最小、最大的个数方案有关。根据这个结论，便可以通过前缀和的思想，来遍历k次操作得到的k+1种不同方案，总结为：删除$2\ast m$个最小值，删除$(k-m)$个最大值$(m\le k)$，再找出k+1种方案里得到剩余元素和的最大值。那么这个方案对应的结果怎么算呢？利用前缀和计算区间和的思想即可。

for _ in range(int(input())):
    n,k=map(int,input().split())
    a=sorted(list(map(int,input().split())))
    ans=0
    s=[0]*(n+1)
    for i in range(n):
        s[i+1]=s[i]+a[i]
    for m in range(k+1):
        ans=max(ans,s[n-(k-m)]-s[2*m])
    print(ans)