Huawei OA 面试真题解析：均衡任务调度（Balanced Task Migration）

A data center has K computing nodes. Each node has a current load T and C CPU cores. The maximum load a single CPU core can handle is 200, so the total capacity of a node is C * 200. The CPU utilization of a node is defined as T / (C * 200).

A sudden spike of tasks occurs on one node. To keep all nodes balanced, you need to migrate tasks from the overloaded node to the other nodes so that the CPU utilizations of all nodes become as equal as possible, while preserving the relative load levels across nodes.

Given the overloaded node’s extra load N, output the amount of additional load that should be assigned to each computing node.

Notes:

• If the overloaded node’s load exceeds the total load capacity of all nodes, no redistribution is needed and the additional load for every node is 0.
• If the overloaded node’s load does not exceed the total capacity of all nodes, the final allocation should be completely balanced, meaning the CPU utilizations of all computing nodes should be equal, with precision no less than 0.001.

Input

• The first line contains N, K.
• The second line contains K integers C[1..K].
• The third line contains K integers T[1..K].

Output

Print the additional load for each node.

Example

Input:
1180
3
45 28 45
6750 4200 6750

Output:
450 280 450

Explanation: The three nodes have 45, 28, and 45 CPU cores, and current loads 6750, 4200, and 6750. After migrating 450, 280, and 450 units of load respectively, their CPU utilizations become equal.

这道华为 OA 面试题考查的是按节点算力比例做负载均衡。每个计算节点都有不同的 CPU 核数，单核最大承载为 200，因此节点总容量是 C×200，关键是把额外负载 N 按照各节点容量占比进行分配，使最终各节点的 CPU 利用率尽量一致；若总负载已经超过所有节点总容量，则直接输出 0。样例中 45、28、45 核对应的分配结果为 450、280、450，本质上就是根据容量比例计算每个节点应增加的负载，并注意输出精度要求。