Acwing第145场周赛

B：套餐设计

链接

给定 m 个食物，其中第 i 个食物的种类为 ai。

请你设计一个食物套餐，对于该套餐：

唯一要求是设计好的套餐必须恰好包含 n 个食物。
具体包含多少种食物，以及包含哪些种类的食物，不做要求，任你安排。
每种食物具体包含多少个，不做要求，任你安排。

我们的目标是通过合理安排套餐中包含的食物内容，从而使得利用给定食物，可以制作出的该套餐的数量越多越好。

输出能够制作出的套餐的最大可能数量。

输入格式

第一行包含两个整数 n,m,。

第二行包含 m 个整数 a1,a2,…,am。

输出格式

一个整数，表示能够制作出的套餐的最大可能数量。

如果根本不可能制作出任何套餐，则输出 0。

数据范围

前 4 个测试点满足 1≤m≤10。
所有测试点满足 1≤n≤100，1≤m≤100，1≤ai≤100。

输入样例1：

1 2	`4 10 1 5 2 1 1 1 2 5 7 2`

输出样例1：

输入样例2：

1
2

100 1
1

输出样例2：

输入样例3：

1 2	`2 5 5 4 3 2 1`

输出样例3：

输入样例4：

1 2	`3 9 42 42 42 42 42 42 42 42 42`

输出样例4：

代码一：朴素版本

找4个食物，一共10个食物，所以在最好情况下有10/4=2个套餐
所以我们便让答案从2开始往下枚举，一但符合条件便输出，最后如果没有输出的话，说明没有条件符合，便输出0

所以什么情况是符合的呢？
我们用个数组记录每个数字（食物）出现的次数，食物1有4个，食物2有3个，食物5有2个，食物7有一个，所以当枚举2个套餐的时候，食物1能为每个套餐提供4/2=2个，食物2和食物5提供3/2=1个，食物7提供0个，加起来正好为4，所以符合条件，结果为2

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
const int N = 110;
int st[N];
int n, m;
bool cmp(int x,int y) {
    return x > y;
}
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int x;
        cin >> x;
        st[x]++;
    }

    vector<int> A;
    for (int i = 1; i < N; i++) {
        if (st[i] > 0) A.push_back(st[i]);
    }

    int k = m / n; 
    for (int i = k; i >= 1; i--) {
        int sum = 0;
        for (int j = 0; j < A.size(); j++) {
            sum += A[j] / i;
        } 
        if (sum >= n) {
            cout << i;
            return 0;
        }
    }
    cout << "0";
    return 0;
}

代码二：二分

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int n, m;
int cnt[N];

bool check(int mid)
{
    int res = 0;
    for (int i = 1; i < N; i ++ )
        res += cnt[i] / mid;
    return res >= n;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i ++ )
    {
        int x;
        scanf("%d", &x);
        cnt[x] ++ ;
    }

    int l = 0, r = m / n;
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }

    printf("%d\n", r);
    return 0;
}

C：分班

链接

某年级一共有 m=n×k个学生，编号 1∼m。

其中，第 i 个学生的学习能力为 ai。

学校计划将这些学生平均分配到 n 个班级，每个班级恰好包含 k 个人。

为了保证全班学生都能跟得上讲课，每个班的讲课速度都等于班级内学习能力最低的学生的学习能力。

学校希望班级之间的学习进度不能相差太多，具体来说，任意两个班级之间的讲课速度的差异都不得超过 l。

在此前提下，学校希望通过合理分班，使得所有班级的讲课速度之和尽可能大。

请你计算并输出所有班级的讲课速度之和的最大可能值。

输入格式

第一行包含三个整数 n,k,l。

第二行包含 m=n×k 个整数 a1,a2,…,am。

输出格式

输出一个整数，表示所有班级的讲课速度之和的最大可能值。

如果不存在满足要求的分班方案，则输出 0。