C++难题洛谷求题解

Question

题目背景
Everyone has its own dream.

题目描述
有 n 个人在野球场上打球，第 i 个人战斗力是 a
i
​
，你需要将他们分成 m 组，第 i 组有
m
n
​
人，保证
m
n
​
为奇数。

定义本组球员的不团结值为 x
i
​
，表示本组所有战斗力值的中位数。

请你给出一种分组方案，使 ∑
i=1
m
​
x
i
​
最小。

输入格式
第一行两个数，n 和 m。

第二行 n 个数，为每个球员的 a
i
​
战斗力值。

输出格式
一个数，代表 ∑
i=1
m
​
x
i
​
的最小值。

输入输出样例
输入 #1复制

9 3
1 2 3 4 5 6 7 8 9
输出 #1复制

12
说明/提示
『本题采用捆绑测试』

对于 100% 的数据，1≤n≤10
6
，1≤a
i
​
≤10
9
，满足 m 一定是 n 的因数且
m
n
​
为奇数。

Subtask 测试点编号 特殊限制 分值
Subtask 1 1∼2 n≤10 10
Subtask 2 3∼5 所有 a
i
​
相等 15
Subtask 3 6∼7 对于 2≤i≤n，有 a
i
​
=a
i−1
​
+1 10
Subtask 4 8∼10 m=1 15
Subtask 5 11∼13 n≤2000 15
Subtask 6 14∼20 无特殊限制 35

Answer 1

让【宝码香车】来帮您解答，本回答参考DeepSeek编写，并整理提供。

如果答案让您满意，请采纳、点赞、关注，非常感谢！
.  
每日一句正能量，让它带给您好心情：学会和自己和解，是一生的修行。
.  

C++题解：最小化分组中位数之和

这个问题要求我们将n个球员分成m组，每组人数为k=n/m（保证k为奇数），并找到一种分组方式使得所有组的中位数之和最小。

解题思路

1. 排序是关键：首先将数组排序，这样我们可以更容易地控制中位数的位置
2. 贪心策略：为了最小化中位数之和，我们应该尽量让较小的数成为中位数
3. 分组方式：最佳策略是从排序后的数组中选取前m个最小的中位数

具体来说：

• 将数组升序排序
• 每组的中位数应该尽可能小
• 最优解是取排序后数组中第k/2, k/2 + k, k/2 + 2k, ..., k/2 + (m-1)k位置的元素之和

代码实现

#include <iostream>
#include <vector>
#include <algorithm>


using namespace std;


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    
    sort(a.begin(), a.end());
    
    int k = n / m;  // 每组人数，保证为奇数
    int median_pos = k / 2;  // 每组中位数的位置
    
    long long sum = 0;
    for (int i = 0; i < m; ++i) {
        sum += a[median_pos + i * k];
    }
    
    cout << sum << endl;
    
    return 0;
}

代码说明

1. 输入处理：使用快速输入方法处理大规模数据
2. 排序：将战斗力数组升序排序
3. 计算中位数位置：每组的中位数位置是该组的中间位置(k/2)
4. 累加中位数：每隔k个元素取一个中位数，并累加它们的值
5. 输出结果：输出最小化的中位数之和

复杂度分析

• 时间复杂度：O(n log n) （主要由排序决定）
• 空间复杂度：O(n) （存储输入数组）

这个解法利用了排序和贪心策略，能够高效地找到最优解。