CF 1701C Schedule Management

有 $n$ 個工人和 $m$ 項工作，每項工作有且僅有一個工人擅長。對於一項工作，如果是擅長的人做用時為 $1$，否則用時為 $2$。求完成所有工作的最小時間。

顯然，每項工作應該儘可能讓擅長的工人去做。考慮二分，每次二分出來一個用時，再把每個工人可以在用時內做的工作加起來判斷。

bool check(int n, int m, const std::vector<int> &pcnt, int time)
{
    for (int i = 1; i <= n; i++)
    {
        int pwork = std::min(pcnt[i], time);
        int npwork = (time - pwork) / 2;
        m -= pwork + npwork;
        if (m <= 0) break;
    }
    return m <= 0;
}

void solve()
{
    int n, m;
    scanf("%d%d", &n, &m);
    std::vector<int> pcnt(n + 1);
    for (int i = 1; i <= m; i++)
    {
        int p;
        scanf("%d", &p);
        pcnt[p]++;
    }
    int l = 0, r = m * 2, ans = -1;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        if (check(n, m, pcnt, mid))
        {
            ans = mid;
            r = mid - 1;
        }
        else
        {
            l = mid + 1;
        }
    }
    printf("%d\n", ans);
}