0%

Educational Codeforces Round 131

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;
}
}