C. Schedule Management Educational Codeforces Round 131 (Rated for Div. 2)

题目传送门

大概思路：

二分时间，找每一个时间能完成的任务，然后找到用时最短且完成任务数>=m的时间

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
#define ll long long
int a[maxn];
int n, m;
bool check(int t)
{
	ll sum = 0;
	for (int i = 1; i <= n; i++)  //遍历所有工人 注意i<=n
	{
		if (a[i] <= t)  //每个工人优先完成自己能较快完成的任务，如果时间有多，就能在剩余时间内完成t-a[i]>>1个任务
		{
			sum += a[i];  
			sum += (t - a[i]) >> 1;
		}
		else
			sum += t;  //时间还不够完成所有能较快完成的任务
	}
	return sum >= m; 
}
int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int t;
	cin >> t;
	while (t--)
	{
		cin >> n >> m;
		for (int i = 1; i <= m; i++)
		{
			int temp;
			cin >> temp;
			a[temp]++;  // 记录每个工人能较快完成的个数
		}
		int l = 1, r = 2 * m;
		while (l < r)  //经典二分，二分时间
		{
			int mid = (l + r) >> 1;
			if (check(mid))r = mid;
			else l = mid + 1;
		}
		cout << l << endl;
		for (int i = 1; i <= m; i++) a[i] = 0;
	}
	return 0;
}