题解：P13759 Basketball

· · 题解

赛事没有过掉，可以退役了。

题意化简

现在有 n 个数组，你要把它们分成 m 组，求出每组中位数相加的结果的最小值。

思路

首先，我们肯定希望中位数越小越好。

那么，我们先从小到大排序，然后，我们计算中位数肯定是最优的，因为我们每次取最优，而且这次的选择与后一次是不相干的。

拿样例举例子：

1 2 3 4 5 6 7 8 9

发现最优的选择是当第 2,4,6 个数字作为中位数最优：

1 2 7

3 4 8

5 6 9

在 m 个数当中，中位数在原数列的位置总是 \lfloor \frac{a \div b}{2} \rfloor 的倍数。

那么，我们枚举一下这个位置，在加到一起就是答案啦！

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,l,ans,a[1000010];
signed main(){
    cin >> n >> m;
    l = n / m / 2 + 1;
    for (int i = 1;i <= n;i++) cin >> a[i];
    sort(a + 1,a + n + 1);
    for (int i = 1;i <= m;i++){
        ans += a[l];
        l += n / m / 2 + 1;
    }
    cout << ans << endl;
}