题目描述

难度分:$1400$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$m$之和$\leq 2 \times 10^5$。

每组数据输入$n$，$m(1 \leq n \leq m \leq 2 \times 10^5)$和长为$m$的数组$a(1 \leq a[i] \leq n)$。

有$n$名工人和$m$个任务，$a[i]$表示擅长第$i$个任务的工人编号。

每个任务只能分配给一名工人。如果工人擅长该任务，他会用$1$小时完成，否则需要$2$小时完成。

一名工人一次只能做一个任务，完成一个任务后，才能开始他的下一个任务。所有工人同时开始工作。输出完成所有任务最少要多少小时。

输入样例

4
2 4
1 2 1 2
2 4
1 1 1 1
5 5
5 1 3 2 4
1 1
1

输出样例

2
3
1
1

算法

二分答案

时间给得越多显然就越能完成任务，因此用一个数组$cnt$记录每个工人擅长的任务数量$cnt[a[i]]$，然后二分完成任务的时间，对于一个给定的时间$x$：

1. 如果工人$i$擅长的任务数量$cnt[i] \geq x$，那他就能花$x$的时间干完$x$个擅长的任务；
2. 如果工人$i$擅长的任务数量$cnt[i] \lt x$，那他只能花$cnt[i]$的时间干完$cnt[i]$个擅长的任务，剩余的$x-cnt[i]$时间要干$[\frac{x-cnt[i]}{2}]$个不擅长的任务（其中$[.]$表示对$.$向下取整）。

遍历所有$i \in [1,n]$计算每个工人干的任务数：如果干完的任务数不小于$m$，说明这个时间$x$是可以的，往左搜索看能不能更小；否则就要往右搜索，宽限完成任务的时间。

复杂度分析

时间复杂度

二分的时间复杂度是$O(log_2m)$，每次二分的$check$要遍历$i \in [1,n]$，时间复杂度为$O(n)$。因此，算法整体的时间复杂度为$O(nlog_2m)$。

空间复杂度

在二分的过程中需要一个$cnt$数组来记录每个工人擅长的任务数，而这个数组的空间消耗是$O(n)$的，这也是整个算法的额外空间复杂度。

C++ 代码

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

using namespace std;
const int N = 200010;
int T, n, m, a[N], cnt[N];

bool check(int x) {
    long long sum = 0;
    for(int i = 1; i <= n; i++) {
        if(cnt[i] >= x) {
            sum += x;
        }else {
            sum += cnt[i] + (x - cnt[i]) / 2;
        }
    }
    return sum >= m;
}

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &n, &m);
        memset(cnt, 0, sizeof cnt);
        for(int i = 1; i <= m; i++) {
            scanf("%d", &a[i]);
            cnt[a[i]]++;
        }
        int l = 1, r = 2*m;
        while(l < r) {
            int mid = l + r >> 1;
            if(check(mid)) {
                r = mid;
            }else {
                l = mid + 1;
            }
        }
        printf("%d\n", r);
    }
    return 0;
}