Schedule Management
Contest: Educational Codeforces Round 131 (Rated for Div. 2)
Difficulty rating: 1400
Tags: binary search, greedy, implementation, two pointers

There are $$$n$$$ workers and $$$m$$$ tasks. The workers are numbered from $$$1$$$ to $$$n$$$. Each task $$$i$$$ has a value $$$a_i$$$ — the index of worker who is proficient in this task.

Every task should have a worker assigned to it. If a worker is proficient in the task, they complete it in $$$1$$$ hour. Otherwise, it takes them $$$2$$$ hours.

The workers work in parallel, independently of each other. Each worker can only work on one task at once.

Assign the workers to all tasks in such a way that the tasks are completed as early as possible. The work starts at time $$$0$$$. What's the minimum time all tasks can be completed by?

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of testcases.

The first line of each testcase contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le m \le 2 \cdot 10^5$$$) — the number of workers and the number of tasks.

The second line contains $$$m$$$ integers $$$a_1, a_2, \dots, a_m$$$ ($$$1 \le a_i \le n$$$) — the index of the worker proficient in the $$$i$$$-th task.

The sum of $$$m$$$ over all testcases doesn't exceed $$$2 \cdot 10^5$$$.

Output format:
For each testcase, print a single integer — the minimum time all tasks can be completed by.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first testcase, the first worker works on tasks $$$1$$$ and $$$3$$$, and the second worker works on tasks $$$2$$$ and $$$4$$$. Since they both are proficient in the corresponding tasks, they take $$$1$$$ hour on each. Both of them complete $$$2$$$ tasks in $$$2$$$ hours. Thus, all tasks are completed by $$$2$$$ hours.

In the second testcase, it's optimal to assign the first worker to tasks $$$1, 2$$$ and $$$3$$$ and the second worker to task $$$4$$$. The first worker spends $$$3$$$ hours, the second worker spends $$$2$$$ hours (since they are not proficient in the taken task).

In the third example, each worker can be assigned to the task they are proficient at. Thus, each of them complete their task in $$$1$$$ hour.

Example input:
4
2 4
1 2 1 2
2 4
1 1 1 1
5 5
5 1 3 2 4
1 1
1

Example output:
2
3
1
1

Editorial:
The statement should instantly scream binary search at you. Clearly, if you can assign the workers in such a way that the tasks are completed by time $$$t$$$, you can complete them all by $$$t+1$$$ or more as well.
How to check if the tasks can be completed by some time $$$t$$$? What that means is that all workers have $$$t$$$ hours to work on some tasks. If all tasks took $$$2$$$ hours to complete, then each of them could complete $$$\lfloor \frac t 2 \rfloor$$$ of them. Thus, together they would be able to complete $$$\lfloor \frac t 2 \rfloor \cdot n$$$ tasks.
How to incorporate the $$$1$$$-hour tasks into that? Well, we can redistribute the tasks in such a way that each worker first completes the tasks they are proficient in, then some other tasks if they have more time.
So the general idea is the following. Let each worker $$$i$$$ complete $$$min(t, \mathit{cnt}_i)$$$ $$$1$$$-hour tasks, where $$$\mathit{cnt}_i$$$ is the number of tasks the $$$i$$$-th worker is proficient in. Then remember how many $$$2$$$-hour tasks they can complete, which is $$$\lfloor \frac{t - min(t, \mathit{cnt}_i)}{2} \rfloor$$$. Finally, remember how many tasks that they are proficient in they didn't have time to complete, which is $$$\mathit{cnt}_i - min(t, \mathit{cnt}_i)$$$. If the sum of the number of incomplete tasks doesn't exceed the sum of the number of tasks they have time to complete, then everything can be completed in time $$$t$$$.
Worst case, it can take up to $$$2m$$$ hours to complete everything — if you assign all tasks to a single worker, and they are not proficient in any of them.
Overall complexity: $$$O(n \log m)$$$ per testcase.