题解 | #中位数#

题目大意：

有个数，每次操作使两个数删掉，留下它们两个的和，问进过次操作后的最小中位数。

思路：

对于初中数学中位数的定义：

1. 对于一个序列长度为奇数时，中位数为序列升序排序后的第
2. 对于一个序列长度为偶数时，中位数为序列升序排序后的第
   那我们缩小中位数的大小，那一定是要将序列中小的数尽可能的位于中间的位置，而大数尽量在边上的位置。
   所以对于这题的贪心就是每次选择一个最大值和次大值将其合并，最后答案就按照题目的方法求出就行了。

Code:

#include <cstdio>
#include <iostream>
#include <algorithm>
#define ll long long

using namespace std;

const int N = 2e5 + 10;
ll T, n, k, a[N], b;

int main()
{
    scanf("%lld", &T);
    while(T--)
    {
        scanf("%lld%lld", &n, &k);
        b = n;
        for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
        sort(a + 1, a + 1 + n);  //将序列进行升序排序
        while(k) k--, b--, a[b] = a[b] + a[b + 1]; //每次选择最大值和次大值合并
        printf("%lld\n", a[(b + 1) / 2]);
    }
    return 0;
}