华为校招 OA 面试真题解析：Balanced Task Scheduling

There are K computing nodes in a data center. The current load of the i-th node is T[i], and the node has C[i] CPU cores. Each CPU core can carry at most 200 units of load, so the maximum load of a node is C[i] * 200.

Tasks can be migrated between nodes to balance the system. After redistribution, the CPU load ratio of every node must be the same.

If the total current load exceeds the total capacity of all nodes, no redistribution is needed and every node should add 0 tasks.

Given N, K, the arrays C and T, compute the number of additional tasks each node should receive so that the final loads are balanced as much as possible. The final balance must be accurate to within 0.001.

Input:

N
K
C[0] C[1] ... C[K-1]
T[0] T[1] ... T[K-1]

Output:

The number of additional tasks for each node.

Example 1:

Input:
1180
3
45 28 45
6750 4200 6750

Output:
450 280 450

Example 2:

Input:
500
3
2 2 2
200 300 400

Output:
0 0 0

这道题的核心是把所有计算节点的 CPU 利用率拉到同一水平：设最终统一的负载比例为 x，则每个节点最终负载应为 C[i] * 200 * x，而需要新增的任务数就是这个目标值减去当前负载 T[i]。关键在于先判断总负载 N 是否已经超过总容量；如果超过，则说明无法再重分配，直接输出 0。否则利用二分搜索在 [0, 1] 范围内寻找最大的可行比例 x，使得所有节点新增任务总和不超过 N，并把每个节点的增量按该比例计算出来，最后注意题目要求精度达到 0.001。