1701C - Schedule Management 二分答案好题

1701C - Schedule Management

Problem - 1701C - Codeforces

题意：

有n个员工，编号为1~n，有m份工作，1≤mi≤n1\\le m_i \\le n1≤mi​≤n 。i号员工做mim_imi​=$i$的工作只需要1个小时（他熟练这份工作），如果做别的工作就需要两个小时（他不熟练份工作）.

求做完所有工作最少需要多少天？

分析：

2022.10.17：

二分答案是一种枚举方法，在一个区间的答案内，找到符合条件的并且最大或者最小（或者满足其他条件）的值，倍增和二分都能得出答案，但是二分好写一点，所以我们使用二分来枚举答案，

【算法1-6】二分查找与二分答案 - 题单 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

‍

结合复杂度2e5和天数是单调递增的，可以使用二分答案来写。

‍

主要是chack函数的写法，要算出在t小时能不能完成工作。（二分就是找到最小的满足情况的值）

首先我们确定二分范围，如果每个工作都要两个小时，那么最大值就是2*m。

一个人t小时能做的不熟练工作数量为⌊t2⌋\\lfloor \\frac t 2 \\rfloor⌊2t​⌋，（这个下取整要反应快！！！想明白）那么n个人就是⌊t2⌋∗n\\lfloor \\frac t 2 \\rfloor *n⌊2t​⌋∗n

我们先用cnt[i]表示编号为i的工作数量。

接下来就写chack函数

首先如果在t小时内，员工i可以完成自己熟练的工作的话，剩余时间就是t-cnt[i]，那么接下来如果他要做别的工作都只能做不熟练的了，也就是他还能做last=(t−cnt[i])2\\frac {(t-cnt[i])} 22(t−cnt[i])​，遍历i，把每个员工的last加起来。

如果t小时内不能完成自己的工作的话，那么剩余的工作数就是more=cnt[i]-t,

如果last>=more也就是剩余工作都能被别帮忙做掉那么就是符合情况的。

#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {int t;cin >> t;while (t--) {int n, k;cin >> n >> k;//这里用k表示m，防止打错vector<int> ve(k + 1);vector<int> mp(k+1,0);for (int i = 1; i <= k; i++) {cin >> ve[i];mp[ve[i]]++;}auto chack = [&](int t) {int last = 0, more = 0;for (int i = 1; i <= n;i++) {if (t >= mp[i]) {last += (t - mp[i]) / 2;//时间足够，last是多出来的时间所能做的工作数} else {more += (mp[i] - t);//时间不够，需要别人来帮忙的工作数量}}// cout << more << ' ' << last << endl;return more <= last;//如果多出来能做的工作数大于等于需要帮忙的工作数，说明在t时间内可以做完。};int l = 0, r = 2 * k, mid;int res;while (l<r) {mid = (r + l) >> 1;// cout << mid << ' ';if (chack(mid)) {//cout << res << endl;// res = mid;r = mid;} else {l = mid+1;}}cout << r << endl;}
}

‍