小鸿给你一个数组a1,a2,...,an，其中所有元素都是不同的。
你必须对其进行k次操作。在每个操作中，你需要做以下两个操作中的一个（每次任选其中之一即可）：
1.找到数组中的两个最小元素，并删除它们；
2.找到数组中的最大元素，并删除它。
小鸿想计算出k次操作后，所得数组的最大元素之和。但这对小鸿来说太难了，你能帮帮他吗？
问题 I: 最大和
时间限制: 2 Sec 内存限制: 256 MB提交: 0 解决: 33
[提交][状态][讨论版][命题人:]
题目描述
输入描述
第一行包含一个整数 t （1≤t≤104） — 测试用例的数量。
每个测试用例由两行组成：
第一行包含两个整数 n和 k （3≤n≤2⋅105; 1≤k≤99999; 2k<n） — 元素和操作的数量。
第二行包含n个整数 a1，a2,...,an （1≤ai≤109;所有 ai不同） — 数组的元素。
数据保证n的总和不超过2⋅105。
每个测试用例由两行组成：
第一行包含两个整数 n和 k （3≤n≤2⋅105; 1≤k≤99999; 2k<n） — 元素和操作的数量。
第二行包含n个整数 a1，a2,...,an （1≤ai≤109;所有 ai不同） — 数组的元素。
数据保证n的总和不超过2⋅105。
输出描述
对于每个测试用例，输出一个整数 — 结果数组中元素的最大可能总和。
样例输入
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是最好的答案。
在第二个测试用例中，最优选择是一次删除两个最小值，一次删除最大值，这样就能得到11。
-
Anything about this OnlineJudge, Please Contact Administrator. Click add QQ
OJ system based on HUSTOJ Project , UI based on Twitter Bootstrap
Copyright 2016 ACM算法攻关部
cnt: 10447
关于网站改版