洛谷刷题C++语言 | P4447 分组 洛谷p1424 c语言

学习C++从娃娃抓起！记录下洛谷C++学习和备考过程中的题目，记录每一个瞬间。

附上汇总贴：洛谷刷题C++语言 | 汇总_热爱编程的通信人的博客-CSDN博客

【题目描述】

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

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

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

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

【输入】

输入有两行：

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

【输出】

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

【输入样例】

7
4 5 2 3 -4 -3 -5

【输出样例】

3

【代码详解】

//最后一个测试点TLE，知道是二分写法，但是没写出来
#include <bits/stdc++.h>
using namespace std;
int n, a[100005], mark=0, ans;
struct team {
    int num, sl;
}ts[100005];
void insert(int k)
{
    int find=0, flag, tnum=100005;
    for (int i=0; i<mark; i++) {
        if (ts[i].sl == k-1) {
            if (ts[i].num<tnum) {
                flag = i;
                find = 1;
                tnum = ts[i].num;
            } 
        }
    }
    if (find==1) {
        ts[flag].sl = k;
        ts[flag].num++;

    } else {
        ts[mark].sl = k;
        ts[mark].num=1;
        mark++;
    }
}
int main()
{
    scanf("%d", &n);
    for (int i=0; i<n; i++) {
        scanf("%d", &a[i]);
    }
    sort(a, a+n);
    for (int i=0; i<n; i++) {
        insert(a[i]);
    }
    ans = ts[0].num;
    for (int i=1; i<mark; i++) {
        if (ts[i].num<ans) {
            ans = ts[i].num;
        }
    }
    printf("%d", ans);
    return 0;
}

【运行结果】

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