题目大意

有n个工人和m个任务，每个任务都有且仅有一个工人擅长做，如果让擅长做的工人去做，那么要花一个单位时间，否则要花两个单位时间。请问完成所有的任务至少要花多少时间。

注意：每项工作只能由一个工人完成，不能合作完成。

输入格式

本题多测，对于每组数据，第一行两个整数n和m。第二行m个数，表示每项工作所擅长的工人编号。

思路分析

本题要求输出最小时间，依旧采用二分的方法，时间单调有界，因此二分时间，在check函数中，比较在mid秒内能否完成，本题难点在于怎么样判断在mid秒内能否完成。首先先记录一个工人擅长的工作出现次数，后将他们依次与mid比较，如果都小于mid，则必行；若有大有小，可以用a记录比mid大的和，此为不擅长做此工作的人需要做的；用b记录比mid小的和/2，此为一些人多余的时间所能做的不擅长的工作，比较a,b。同时注意了l.r向上取整。

#include<bits/stdc++.h>using namespace std;const int N=200005;int n,m,f[N],t,x,mid;long long a,b;bool check(int mid){a=b=0;for(int i=1;i<=n;i++){if(mid<=f[i]) a+=f[i]-mid;else b+=(mid-f[i])/2;}return a<=b;}int main(){cin>>t;while(t--){cin>>n>>m;for(int i=1;i<=m;i++) cin>>x,f[x]++;//记录一个编号出现的次数int l=1,r=m*2;while(l<r){mid=l+r>>1;if(check(mid))r=mid;else l=mid+1;}cout<<l<<endl;for(int i=1;i<=n;i++)f[i]=0;}return 0;}