洛谷P4447 [AHOI2018初中组] 分组（C++代码讲解）

1.题目

题目描述：

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

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

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

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

输入格式：

输入有两行：

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

输出格式：

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

输入输出样例：

输入 #1

7
4 5 2 3 -4 -3 -5

输出 #1

说明/提示：

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

【数据范围】

对于 100% 的数据满足：1≤n≤100000，∣ai∣≤10^9。

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

测试点编号	数据限制
1∼2	n≤6,1≤ai≤100
3∼4	n≤1000,1≤ai≤10^5 且 ai 互不相同
5∼6	n≤100000,ai 互不相同
7∼8	n≤100000,1≤ai≤10^5
9∼10	n≤100000,−10^9≤ai≤10^9

2.具体思路

题目的大概意思就是，我们要让最少人数的队伍人数尽可能的多一些。

所以我有以下思路：

先把所有组员按照实力大小排好序，实力小的在前；
然后从头到尾一个一个地插入到符合插入要求的队伍中，注意符合插入要求的队伍可能会有多个，当有多个队伍符合要求时，因为我们要使得最少人数的队伍人数尽量多一些，所以我们要插入到人数最少的那个队伍；
在插入完后，我们只需要遍历一下所有队伍，找出最少人数的队伍即可。

我所遇到的问题：

最后一个测试点运行超时。

错误原因分析：

使用冒泡排序寻找符合插入要求的队伍。冒泡排序太消耗时间了。

我的改进：

使用二分查找寻找符合插入要求的队伍。

那么使用二分查找怎么找到多个符合插入要求的队伍呢？

我们在使用二分查找时，找到一个符合插入要求的队伍的下标，然后在此坐标基础上向左和向右查找是否还存在满足要求的队伍。

3.代码讲解

#include <iostream>
#include <algorithm>

#define MAX 100000
using namespace std;

struct team
{
    // end表示队伍中的队员的最大实力，length来记录队伍人数
    int end;
    int length = 0;
};

bool my_Compare( struct team a, struct team b )
{
    return a.end < b.end;
}

int main()
{
    int n;
    cin >> n;
    long long num[n];
    int i;
    for( i = 0; i < n ; i++)
    {
        cin >> num[i];
    }
    sort( num, num + n);

    struct team minTeam[MAX];
    minTeam[0].end = num[0];
    minTeam[0].length = 1;
    int count = 1;
    for( i = 1; i < n; i++)
    {
        // 用一个数组来存储可以插入的队位置
        int lct[MAX] = {-1}, j = 0;
        // 注意我们在上面已经将所有组员按实力大小排好序了，所以后面插入组员的实力肯定要大于等于前面的，
        // 那么我们只需要考虑一个队里面实力最大的人和要插入的组员的实力的比较就可以了。
        int low = 0, high = count;
        while( low <= high )
        {
            int mid = low + ( high - low ) / 2;
            if( minTeam[mid].end == num[i] - 1 )
            {
                lct[j++] = mid;
                break;
            }
            else if( num[i] - 1 > minTeam[mid].end )
            {
                low = mid + 1;
            }
            else
            {
                high = mid - 1;
            }
        }
        // 如果没有可插入的队，就直接新建一个
        if( lct[0] == -1 )
        {
            minTeam[count].end = num[i];
            minTeam[count].length = 1;
            count++;
            continue;
        }
        // 找到一个可插入的队后，我们还要考虑到是否存在多个可插入队，如果存在我们要把人插在人数最少的队
        // 因为每次我们都根据各个队伍中实力最强的队员按大小对队伍进行排序，所以可插入的队一定连续的
        // 向左边寻找
        for( int p = lct[0] - 1; p >= 0; p--)
        {
            if( num[i] - 1 == minTeam[p].end )
            {
                lct[j++] = p;
            }
            else
            {
                break;
            }
        }
        // 向右边寻找
        for( int p = lct[0] + 1; p < count; p++)
        {
            if( num[i] - 1 == minTeam[p].end )
            {
                lct[j++] = p;
            }
            else
            {
                break;
            }
        }
        // 在可插入的队中，找出人数最少的队
        int min = minTeam[lct[0]].length, biao = lct[0];
        for( int p = 1; p < j; p++)
        {
            if( min > minTeam[lct[p]].length )
            {
                min = minTeam[lct[p]].length;
                biao = lct[p];
            }
        }
        // 插入符合的队伍
        minTeam[biao].end = num[i];
        minTeam[biao].length++;

        // 按照队员最大实力排序
        sort( minTeam, minTeam + count, my_Compare);
    }

    int min = minTeam[0].length;
    for( i = 0; i < count; i++)
    {
        if( min > minTeam[i].length )
        {
            min = minTeam[i].length;
        }
    }
    cout << min;
    return 0;
}