玖的数学&算法录
0%

Educational Codeforces Round 131

发表于 更新于
本文字数： 1.1k 阅读时长 ≈ 1 分钟

Educational Codeforces Round 131 (Rated for Div. 2)

补题记录

C. Schedule Management（1400）

题意：有n个工人和m个工作，工人从1到n编号，每第i个任务都有一个值ai表示精通该任务的工人的指数

每个任务都应该有一个工人分配给他，如果工人精通这项任务，他们会在1小时内完成，否则需要2个小时，每个工人独立并行工作，一次只能完成一项任务，问从时间0开始，完成所有任务的最短时间是多少？

3

Input：

$$1 \leq t \leq 10^4 , 1 \leq n \leq m \leq 2 \cdot 10 ^5 , \forall a_i \in [1,n] , \sum m < 2 \cdot 10^5 $$

方法：

二分
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
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pb push_back
const int MAXN = 2e5 + 10;
int a[MAXN],cnt[MAXN];
using namespace std;

int n,m;
bool check(int mid){
    ll res = 0;
    for(int i=1;i<=n;i++){
        if(cnt[i] <= mid){
            res += (mid - cnt[i]) / 2;
        } else{
            res -= (cnt[i] - mid);
        }
    }
    return res >= 0;
}
int main(){
    int T;
    cin >> T;
    while(T--){
        cin >> n >> m;
        int l = 1 , r = 0;
        for(int i=1;i<=n;i++){
            cnt[i] = 0;
        }
        for(int i=1;i<=m;i++) {
            cin >> a[i];
            cnt[a[i]]++;
        }
        for(int i=1;i<=n;i++){
            r = max(r,cnt[i]);
        }
        while(l < r){
            int mid = l + r >> 1;
            if(check(mid)){
                r = mid;
            } else{
                l = mid + 1;
            }
        }
        cout << r << endl;
    }
}