题解思路

本题要求将宕机节点的负载均匀分配给其他节点，以确保各个节点的CPU负载保持相等。每个节点的CPU负载是节点当前负载与节点总容量的比值。以下是具体的步骤和解题思路：

1. 总体分析

• 假设当前有K个节点，其中每个节点具有C个CPU核心。每个核心的最大负载为200，因此节点的总容量为 C * 200。
• 计算宕机节点负载总和 N 后，目标是通过均匀分配该负载，使得所有节点的CPU负载比率保持一致。

2. 目标负载比率的确定

• 首先，计算当前系统的总负载，即所有节点的当前负载之和加上宕机节点的负载 N。可以表示为 总负载 = N + sum(T)，其中sum(T)为各节点当前负载的和。
• 然后，计算系统的总容量，即各节点核心数之和乘以单个核心的最大负载 200。即 总容量 = sum(C) * 200。
• 接下来，计算最终所有节点需要达到的负载比率 rate，计算方式为：$$rate = \frac{N + \sum T}{200 * \sum C}$$ 这个rate表示每个节点在分配负载后的目标CPU负载率。

3. 计算各节点的新增负载量

• 设节点i的核心数为C_i，当前负载为T_i，则分配后的目标负载为 目标负载 = rate * C_i * 200。
• 每个节点需要新增的负载 a_i 为： [ a_i = \text{目标负载} - T_i = rate * C_i * 200 - T_i ]
• 对于每个节点，我们可以计算出新增负载 a_i。如果计算出的总负载超过系统总容量 sum(C) * 200，则无法分配新增负载，直接输出每个节点的新增负载为 0。

4. 边界条件

• 当N + sum(T) > sum(C) * 200时，宕机节点的负载总和超出所有节点的剩余容量。根据题意，这种情况下直接输出所有新增负载为 0。

复杂度分析

• 时间复杂度：O(K)，遍历每个节点计算总负载和新增负载量，因此线性时间复杂度。
• 空间复杂度：O(K)，存储各个节点的CPU核心数、当前负载及计算后的新增负载。

代码

python

# 输入
wait_load = int(input())
n = int(input())
cpu = list(map(int, input().split()))
cur_load = list(map(int, input().split()))

global total_load
total_load = wait_load + sum(cur_load)

# 检查宕机节点负载数是否超过总负载
if total_load > sum(cpu) * 200:
    for _ in range(n):
        print(0, end=" ")
else:
    result_ratio = total_load/(200*sum(cpu))
    ans = [int(result_ratio*200*cpu[i] - cur_load[i]) for i in range(n)]

    for i in range(n):
        print(ans[i],end=" ")

Java

import java.util.Scanner;
import java.util.Arrays;

public class LoadBalancer {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 输入宕机节点总负载
        int waitLoad = scanner.nextInt();
        // 输入节点数量
        int n = scanner.nextInt();
        
        // 输入每个节点的CPU容量
        int[] cpu = new int[n];
        for (int i = 0; i < n; i++) {
            cpu[i] = scanner.nextInt();
        }
        
        // 输入每个节点当前的负载
        int[] curLoad = new int[n];
        for (int i = 0; i < n; i++) {
            curLoad[i] = scanner.nextInt();
        }
        
        // 计算总负载，包含宕机节点的负载和所有节点的当前负载
        int totalLoad = waitLoad + Arrays.stream(curLoad).sum();
        
        // 检查是否总负载超过了总CPU容量能承受的最大负载
        if (totalLoad > Arrays.stream(cpu).sum() * 200) {
            // 如果超过了，则无法分配，返回每个节点分配0
            for (int i = 0; i < n; i++) {
                System.out.print(0 + " ");
            }
        } else {
            // 计算负载比例
            double resultRatio = (double) totalLoad / (200 * Arrays.stream(cpu).sum());
            // 根据比例计算每个节点需要分配的额外负载
            for (int i = 0; i < n; i++) {
                int a_i = (int) (resultRatio * 200 * cpu[i] - curLoad[i]);
                System.out.print(a_i + " ");
            }
        }

        scanner.close();
    }
}

C++

#include <iostream>
#include <vector>
#include <numeric>  // for accumulate
using namespace std;

int main() {
    // 输入宕机节点总负载
    int wait_load;
    cin >> wait_load;

    // 输入节点数量
    int n;
    cin >> n;

    // 输入每个节点的CPU容量
    vector<int> cpu(n);
    for (int i = 0; i < n; i++) {
        cin >> cpu[i];
    }

    // 输入每个节点当前的负载
    vector<int> cur_load(n);
    for (int i = 0; i < n; i++) {
        cin >> cur_load[i];
    }

    // 计算总负载，包含宕机节点的负载和所有节点的当前负载
    int total_load = wait_load + accumulate(cur_load.begin(), cur_load.end(), 0);

    // 检查是否总负载超过了总CPU容量能承受的最大负载
    if (total_load > accumulate(cpu.begin(), cpu.end(), 0) * 200) {
        // 如果超过了，则无法分配，返回每个节点分配0
        for (int i = 0; i < n; i++) {
            cout << 0 << " ";
        }
    } else {
        // 计算负载比例
        double result_ratio = static_cast<double>(total_load) / (200 * accumulate(cpu.begin(), cpu.end(), 0));
        // 根据比例计算每个节点需要分配的额外负载
        for (int i = 0; i < n; i++) {
            int a_i = static_cast<int>(result_ratio * 200 * cpu[i] - cur_load[i]);
            cout << a_i << " ";
        }
    }

    return 0;
}

OJ会员可以通过点击题目上方《已通过》查看其他通过代码来学习。

题目内容

机房运行了$K$个计算节点，每个节点当前负载数为$T$，每个节点的$CPU$核心数为$C$，一个$CPU$核心的最大负载数为$200$，节点总负载数=节点$CPU$核心数$*200$，节点的$CPU$负载-节点当前负载数/节点总负载数。节点宕机在机房是经常发生的事，因此要设计一种算法将宕机节点的负载均衡地迁移到负载低的节点，使各节点的$CPU$负载保持一致，给定右机节点的负载数$N$，求每个计算节点应该新增的负载数。 备注:$1$.如果宕机节点的负载数超出了所有节点总负载数，不进行重新调度，则每个节点新增的任务数为$0$。

2.如果宕机节点的负载数没有超出所有节点总负载数，输入能够保证最终分配完全均衡，即分配后各个计算节点的$CPU$负载保持相等，精度不低于$0.001$。

输入描述

宕机节点的负载数$N$[$1,1000000$]

计算节点的台数$K$[$1,500$]

每个节点的核心数$C$[$1,1000$]

每个节点当前的负载数$T$[$1,10000$]

输出描述

每个节点应该新增的负载数。

样例1

输入

 1180
 3
 45 28 45
 6750 4200 6750

输出

450 280 450

说明

宕机节点上有$1180$个负载待迁移，计算节点有$3$个，$CPU$核心数分别为$45、28、45$，当前负载分别为$6750、4200、6750$。

三个节点分别迁移$450、280、450$个负载后，节点的$CPU$负载分别为$(450+6750)/(45×200)=0.8$、$(280+4200)/(28×200)=0.8$、$(450+6750)/(45×200)=0.8$，所以返回了$450\ 280\ 450$。

样例2

输入

500
3
2 2 2
200 300 400

输出

0 0 0

说明

宕机节点上有$500$个负载待迁移，计算节点有$3$个，每个节点有$2$个核心各个节点分别有$200$个，$300$个、$400$个负载。第$1$个计算节点还能增加$200$个负载，第$2$个计算节点还能增加$100$个负载，第$3$个计算节点无法增加负载，$3$个计算总共能增加的负载为$300$，小于$500$，因此不进行重新调度，返回$0\ 0\ 0$。