P4447 [AHOI2018初中组]分组——贪心

[AHOI2018初中组]分组

题目描述

小可可的学校信息组总共有 $n$ 个队员，每个人都有一个实力值 $a_i$。现在，一年一度的编程大赛就要到了，小可可的学校获得了若干个参赛名额，教练决定把学校信息组的 $n$ 个队员分成若干个小组去参加这场比赛。

但是每个队员都不会愿意与实力跟自己过于悬殊的队员组队，于是要求分成的每个小组的队员实力值连续，同时，一个队不需要两个实力相同的选手。举个例子：$[1,2,3,4,5]$ 是合法的分组方案，因为实力值连续；$[1,2,3,5]$ 不是合法的分组方案，因为实力值不连续；$[0,1,1,2]$ 同样不是合法的分组方案，因为出现了两个实力值为 $1$ 的选手。

如果有小组内人数太少，就会因为时间不够而无法获得高分，于是小可可想让你给出一个合法的分组方案，满足所有人都恰好分到一个小组，使得人数最少的组人数最多，输出人数最少的组人数的最大值。

注意：实力值可能是负数，分组的数量没有限制。

输入格式

输入有两行：

第一行一个正整数 $n$，表示队员数量。
第二行有 $n$ 个整数，第 $i$ 个整数 $a_i$ 表示第 $i$ 个队员的实力。

输出格式

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

样例 #1

样例输入 #1

7
4 5 2 3 -4 -3 -5
1
2

样例输出 #1

3
1

提示

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

【数据范围】

对于 $100\%$ 的数据满足：$1\le n\le 100000$，$|a_i|\le 10^9$。

本题共 $10$ 个测试点，编号为 $1\sim 10$，每个测试点额外保证如下：

分析

1. 此题就是导弹拦截系统的升级版贪心问题，一个分组就是一个拦截系统，每个导弹拦截系统只能拦截和自己差值为1也就是连续的导弹，然后对于一个导弹，遍历cnt个导弹拦截系统，看看哪个可以容下他，只不过这题需要使用的系统是：用cnt个当中拦截过导弹数量最少的系统；可参考导弹拦截系统：1322：【例6.4】拦截导弹问题(Noip1999)——贪心
   

2. 样例分析：13
   -5 -5 -4 -4 -3 -3 2 3 3 4 4 4 5
   分组结果：
   -5 -4 -3
   -5 -4 -3
   2 3 4
   3 4
   4 5

3. 贪心策略：先排序，对于某个数a[i]，遍历cnt个已存在分组，看看a[i]是否和某个分组 j 匹配上（也就是和分组里面的元素值连续起来），可以的话，记录当前较优解，找拥有元素最少的分组，记录下他的分组编号minLenIdx，和元素个数minLen；然后遍历完cnt个分组，决定如何处理a[i]，是否重开一组还是放在编号minLenIdx的分组里面；

#include

using namespace std;

int n, ans = 100010;
int a[100010];
int cnt;//分组的个数
int last[100010];//分组的最后一个元素的值
int len[100010];//分组的长度

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    sort(a + 1, a + 1 + n);
    //先初始第一个分组
    last[++cnt] = a[1];
    len[cnt] = 1;
    for (int i = 2; i <= n; ++i) {
        int minLenIdx = -1;//拥有元素最少的分组编号
        int minLen = 100010;//拥有元素最少的分组的元素个数
        //遍历cnt个分组，看看可以放下哪个
        for (int j = 1; j <= cnt; j++) {
            if (a[i] - last[j] == 1) {//和第j个分组的元素连续
                if (len[j] < minLen) {//取拥有元素少的分组
                    minLen = len[j];
                    minLenIdx = j;
                }
            }
        }
        //处理a[i]
        if (minLenIdx == -1) {
            //需要新开一组
            last[++cnt] = a[i];
            len[cnt] = 1;
        } else {
            //填充在编号为minLenIdx组
            last[minLenIdx] = a[i];
            len[minLenIdx]++;
        }
    }
    for (int i = 1; i <= cnt; ++i) {
        ans = min(ans, len[i]);
    }
    cout << ans;
    return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50