UPC8764: 分组

题目描述

小可可的学校信息组总共有 n 个队员，每个人都有一个实力值 a[i]。现在，一年一度的编程大赛就要到了，小可可的学校获得了若干个参赛名额，教练决定把学校信息组的 n 个队员分成若干个小组去参加这场比赛。
但是每个队员都不会愿意与实力跟自己过于悬殊的队员组队，于是要求分成的每个小组的队员实力值连续，同时，一个队不需要两个实力相同的选手。举个例子：
[1, 2, 3, 4, 5]是合法的分组方案，因为实力值连续；
[1, 2, 3, 5]不是合法的分组方案，因为实力值不连续；
[0, 1, 1, 2]同样不是合法的分组方案，因为出现了两个实力值为 1 的选手。
如果有小组内人数太少，就会因为时间不够而无法获得高分，于是小可可想让你给出一个合法的分组方案，满足所有人都恰好分到一个小组，使得人数最少的组人数最多，输出人数最少的组人数的最大值。
注意：实力值可能是负数，分组的数量没有限制。

输入

输入有两行：
第一行一个正整数n，表示队员数量。
第二行有n个整数，第i个整数a[i]表示第i个队员的实力。

输出

输出一行，包括一个正整数，表示人数最少的组的人数最大值。

样例输入

复制样例数据

7
4 5 2 3 -4 -3 -5

样例输出

3

提示

分为2组，一组的队员实力值是{4,5,2,3}，一组是{-4,-3,-5}，其中最小的组人
数为3，可以发现没有比3更优的分法了。

 

贪心解法：按从小到大顺序给人排序，对于每一个人，将其加入人数最少的小组，最终可使人数最少的小组人数最多。

#include "bits/stdc++.h"

using namespace std;

const int inf = 0x3f3f3f3f;
const int maxn = 1e5 + 100;
int a[maxn];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    sort(a, a + n);
    map<int, priority_queue<int, vector<int>, greater<int> > > team;
    map<int, priority_queue<int, vector<int>, greater<int> > >::iterator it;
    int cur;
    for (int i = 0; i < n; i++) {
        cur = 0;
        it = team.find(a[i] - 1);
        if (it != team.end()) {
            if (it->second.size()) {
                cur = it->second.top();
                it->second.pop();
            }
        }
        cur++;
        team[a[i]].push(cur);
    }
    int ans = inf;
    for (it = team.begin(); it != team.end(); it++) {
        if (!it->second.empty()) {
            ans = min(ans, it->second.top());
        }
    }
    if (ans >= inf) ans = 0;
    printf("%d
", ans);
    return 0;
}