专栏文章

题解：P13759 Basketball

wweifengzhaomi
P13759题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio94i1g
此快照首次捕获于
2025/12/02 15:23
3 个月前
此快照最后确认于
2025/12/02 15:23
3 个月前
查看原文
赛事没有过掉，可以退役了。

题意化简

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

思路

首先，我们肯定希望中位数越小越好。
那么，我们先从小到大排序，然后，我们计算中位数肯定是最优的，因为我们每次取最优，而且这次的选择与后一次是不相干的。
拿样例举例子：
1 2 3 4 5 6 7 8 9
发现最优的选择是当第 2,4,62,4,6 个数字作为中位数最优：
1 2 7
3 4 8
5 6 9
在 mm 个数当中，中位数在原数列的位置总是 ⌊a÷b2⌋\lfloor \frac{a \div b}{2} \rfloor 的倍数。
那么，我们枚举一下这个位置，在加到一起就是答案啦！

代码

CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...