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 450Example 2:
Input:
500
3
2 2 2
200 300 400
Output:
0 0 0The key idea is to equalize the final CPU load ratio across all nodes. If the common ratio is x, then the target load of node i is C[i] * 200 * x, so the added tasks for that node are target – T[i]. First check whether the total load N exceeds the total capacity; if so, no redistribution is performed and all outputs are 0. Otherwise, binary search the maximum feasible ratio x in [0, 1], verify the total added tasks do not exceed N, and compute each node’s increment with 0.001-level precision.
