初始化
-
读取输入数据，并找出最大值 作为理想负荷。
-
按照从大到小的顺序对数组进行排序。
贪心策略划分集合
-
使用 小根堆 (priority_queue) 维护当前所有集合的负荷。
-
依次将数字加入当前负荷最小的集合。
求最优
-
遍历 ，计算每种情况的偏差之和。
-
记录最小偏差，并在多个最优解中选择最大的 。
#include <bits/stdc++.h>
using namespace std;
vector<int> arr(1000); // 存储输入的整数
// 结构体表示一个集合的负荷
struct subset {
int load; // 当前负荷
int idx; // 集合索引（用于区分）
};
// 自定义比较函数，建立小根堆（负荷最小的集合优先）
struct cmp {
bool operator()(const subset &a, const subset &b) const {
return a.load > b.load;
}
};
// 计算给定 N 和 M 时的偏差之和
int calculate(int N, int M) {
priority_queue<subset, vector<subset>, cmp> minheap;
// 初始化 N 个空集合
for (int i = 0; i < N; i++) {
minheap.push({ 0, i });
}
// 依次将数字分配给当前负荷最小的集合
for (int i = 0; i < arr.size(); i++) {
subset mintop = minheap.top(); // 取负荷最小的集合
minheap.pop();
mintop.load += arr[i]; // 加入当前整数
minheap.push(mintop); // 放回堆中
}
// 计算所有集合的偏差之和
int dev = 0;
while (!minheap.empty()) {
subset a = minheap.top();
minheap.pop();
dev += abs(a.load - M); // 计算偏差
}
return dev;
}
// 寻找使偏差最小的 N
int find_best_n() {
sort(arr.rbegin(), arr.rend()); // 按降序排序
int M = arr[0]; // 最大值 M
int K = arr.size();
int minD = INT_MAX; // 记录最小偏差
int bestN = 0;
for (int N = 1; N <= K; N++) {
int dev = calculate(N, M);
if (dev < minD) {
minD = dev;
bestN = N;
} else if (dev == minD) {
bestN = max(bestN, N); // 取最大的 N
}
}
return bestN;
}
int main() {
int K;
cin >> K;
for (int i = 0; i < K; i++) {
cin >> arr[i];
}
cout << find_best_n() << endl;
return 0;
}