CF 1701C Schedule Management

標籤： cf

有 $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);
}