There are n jobs that can be executed in parallel on a processor, where the execution time of the i-th job is executionTime[i].
To speed up execution, the following strategy is used.
In one operation, a job is chosen as the major job and is executed for x seconds. All other jobs are executed for y seconds, where y < x.
A job is complete when it has been executed for at least executionTime[i] seconds, then it exits the pool.
Find the minimum number of operations in which the processor can completely execute all the jobs if run optimally.
Example
Consider n = 5, executionTime = [3, 4, 1, 7, 6], x = 4, and y = 2.
The following strategy is optimal using 1-based indexing.
- Choose job 4 as the major job and reduce the execution times of job 4 by
x = 4and of other jobs byy = 2.
NowexecutionTime = [1, 2, -1, 3, 4]. Job 3 is complete, so it is removed. - Choose job 4. Now
executionTime = [-1, 0, -3, -1, 2]. Jobs 1, 2, and 4 are complete. - Choose job 5. Now
executionTime = [-, -, -, -, -2]. Job 5 is complete.
It takes 3 operations to execute all the jobs, so the answer is 3.
Function Description
Complete the function getMinimumOperations in the editor below.
getMinimumOperations has the following parameters:
INTEGER_ARRAY executionTimeINTEGER xINTEGER y
Returns
INTEGER: the minimum number of operations in which the processor can complete the jobs
Constraints
1 <= n <= 10^51 <= executionTime[i] <= 10^91 <= y < x <= 10^9
Sample Input 0
5
3
3
6
3
9
3
2Sample Output 0
3Explanation 0
- Choose job 5, then
executionTime = [1, 1, 4, 1, 6]. All jobs are still in the pool. - Choose job 5, then
executionTime = [-1, -1, 2, -1, 3]. Jobs 1, 2, and 4 are complete. - Choose job 5, then
executionTime = [-, -, 0, -, 0]. Jobs 3 and 5 are complete.
It takes 3 operations to execute all the jobs.
这题的关键是把“每次选择一个主任务，其他任务也会同步推进”的过程，转化为一个可判定的最小操作数问题。因为每次操作对所有任务的影响是固定的：被选中的任务减少 x，其他任务减少 y，所以如果总共做了 k 次操作，每个任务至少会获得 k * y 的基础推进，而它还需要额外被选中若干次才能补足差值。于是可以二分答案 k，检查在 k 次操作内，所有任务所需的额外主任务次数之和是否不超过 k。判断时对每个 executionTime[i] 计算在仅靠 y 推进后还剩多少，再除以 x – y 得到还需多少次被选中，累加后与 k 比较即可。整体做法通常是排序或直接遍历配合整数除法，时间复杂度可做到 O(n log n) 或 O(n log V)，适合 n 到 1e5 的约束。
