🍭 大家好这里是 春秋招笔试突围，一起备战大厂笔试

💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 大厂实习经历

✨ 本系列打算持续跟新 春秋招笔试题

👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸

✨ 笔试合集传送们 -> 🧷春秋招笔试合集

🍒 本专栏已收集 100+ 套笔试题，笔试真题 会在第一时间跟新

🍄 题面描述等均已改编，如果和你笔试题看到的题面描述不一样请理解，做法和题目本质基本不变。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力 💞

🌈 华为秋招(海外留学生版)笔试，来啦！！！

🍥 留学生的题目难度相对于国内来说总体来看会简单一丢丢，但整体题目风格，难度，几乎都是一样的哦～

tips 国内的有些题会复用留学生考过的题目哦，国内机考的朋友可以把留学生的题目也刷一刷

1️⃣ 推公式/枚举/二分，这题的做法很多，由于数据比较小，大家怎么做都可以哈

2️⃣ 模拟题，华子最喜欢的阅读理解+模拟，建议大家多练！！！

3️⃣ 力扣原题改编，今年秋招华为出了很多这种力扣的改编题，基本二三两题都是有出处的，大家平时没事可以多刷刷扣子，打打牛客/力扣的周赛。

📊 01.数据中心负载均衡 评测链接🔗

问题描述

LYA 公司运营着一个大型数据中心，该中心包含 个计算节点。每个节点都有特定数量的 CPU 核心和当前负载。不幸的是，一个节点突然宕机，现在需要将其负载均衡地分配到其他节点上。

每个节点的 CPU 核心数为 ，当前负载数为 。一个 CPU 核心的最大负载数为 200，因此节点的总负载容量为 。节点的 CPU 负载率定义为：当前负载数 / 总负载容量。

宕机节点的负载数为 。您的任务是设计一种算法，将这些负载均衡地分配到其他节点上，使得分配后所有节点的 CPU 负载率保持一致。

请注意以下两点：

1. 如果宕机节点的负载数超过了所有其他节点的剩余容量总和，则不进行重新分配，每个节点新增的负载数为 0。
2. 如果可以进行分配，输入保证最终可以实现完全均衡，即分配后各个计算节点的 CPU 负载率相等，精度不低于 0.001。

输入格式

第一行包含一个整数 ，表示宕机节点的负载数。

第二行包含一个整数 ，表示计算节点的数量。

第三行包含 个整数，表示每个节点的 CPU 核心数 。

第四行包含 个整数，表示每个节点当前的负载数 。

输出格式

输出一行，包含 个整数，表示每个节点应该新增的负载数。

样例输入1

1180
3
45 28 45
6750 4200 6750

样例输出1

450 280 450

样例输入2

500
3
2 2 2
200 300 400

样例输出2

0 0 0

样例解释

样例 解释说明

样例1	宕机节点有 1180 个负载需要迁移。有 3 个计算节点，CPU 核心数分别为 45、28、45，当前负载分别为 6750、4200、6750。分配 450、280、450 个负载后，三个节点的 CPU 负载率均为 0.8。
样例2	宕机节点有 500 个负载需要迁移。有 3 个计算节点，每个有 2 个核心，当前负载分别为 200、300、400。所有节点总共只能增加 300 个负载，小于 500，因此不进行重新分配。

数据范围

• 
• 
• 
• 

题解

二分/推公式/枚举

本题可以二分计算，直接推公式计算，数据范围也比较小，也可以直接枚举计算。

我们这里采用二分来实现

二分步骤：

1. 首先，需要判断是否有足够的容量来容纳宕机节点的负载。如果没有，我们就直接返回全 0 的结果。

2. 如果有足够的容量，我们就需要找到一个合适的负载率，使得所有节点达到这个负载率后，刚好分配完宕机节点的所有负载。

3. 关键点在于如何找到这个合适的负载率。我们可以使用二分查找来解决这个问题。

4. 二分查找的下界是当前所有节点的最大负载率，上界是 1（因为负载率不可能超过 1）。

5. 对于每个猜测的负载率，我们计算需要分配给每个节点的负载数，然后求和看是否等于宕机节点的负载数。

6. 如果和小于宕机节点的负载数，说明猜测的负载率太小；如果和大于宕机节点的负载数，说明猜测的负载率太大。

7. 通过不断调整猜测的负载率，我们最终可以找到一个精确到 0.001 的解。

时间复杂度分析：

• 二分查找的次数是 ，也就是 ，是一个常数。
• 每次二分查找中，我们需要遍历所有节点，复杂度为 。
• 因此，总的时间复杂度是 ，对于给定的 ，这个复杂度是完全可以接受的。

参考代码

• Python

def distribute_load(N, K, C, T):
    # 检查是否有足够的容量
    total_capacity = sum(200 * c - t for c, t in zip(C, T))
    if total_capacity < N:
        return [0] * K

    # 二分查找合适的负载率
    left, right = max(t / (200 * c) for c, t in zip(C, T)), 1.0
    while right - left > 1e-6:
        mid = (left + right) / 2
        allocated = sum(max(0, int(200 * c * mid) - t) for c, t in zip(C, T))
        if allocated < N:
            left = mid
        else:
            right = mid

    # 计算每个节点应该新增的负载数
    result = [max(0, int(200 * c * right) - t) for c, t in zip(C, T)]
    
    # 处理可能的舍入误差
    diff = N - sum(result)
    for i in range(K):
        if diff > 0 and result[i] < 200 * C[i] - T[i]:
            result[i] += 1
            diff -= 1
        if diff == 0:
            break

    return result

# 读取输入
N = int(input())
K = int(input())
C = list(map(int, input().split()))
T = list(map(int, input().split()))

# 计算并输出结果
result = distribute_load(N, K, C, T)
print(*result)

• Java

import java.util.*;

public class Main {
    public static int[] distributeLoad(int N, int K, int[] C, int[] T) {
        // 检查是否有足够的容量
        long totalCapacity = 0;
        for (int i = 0; i < K; i++) {
            totalCapacity += 200L * C[i] - T[i];
        }
        if (totalCapacity < N) {
            return new int[K];
        }

        // 二分查找合适的负载率
        double left = 0, right = 1.0;
        for (int i = 0; i < K; i++) {
            left = Math.max(left, (double) T[i] / (200 * C[i]));
        }

        while (right - left > 1e-6) {
            double mid = (left + right) / 2;
            long allocated = 0;
            for (int i = 0; i < K; i++) {
                allocated += Math.max(0, (int)(200 * C[i] * mid) - T[i]);
            }
            if (allocated < N) {
                left = mid;
            } else {
                right = mid;
            }
        }

        // 计算每个节点应该新增的负载数
        int[] result = new int[K];
        int sum = 0;
        for (int i = 0; i < K; i++) {
            result[i] = Math.max(0, (int)(200 * C[i] * right) - T[i]);
            sum += result[i];
        }

        // 处理可能的舍入误差
        int diff = N - sum;
        for (int i = 0; i < K && diff > 0; i++) {
            if (result[i] < 200 * C[i] - T[i]) {
                result[i]++;
                diff--;
            }
        }

        return result;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int K = scanner.nextInt();
        int[] C = new int[K];
        int[] T = new int[K];

        for (int i = 0; i < K; i++) {
            C[i] = scanner.nextInt();
        }
        for (int i = 0; i < K; i++) {
            T[i] = scanner.nextInt();
        }

        int[] result = distributeLoad(N, K, C, T);
        for (int i = 0; i < K; i++) {
            System.out.print(result[i] + (i == K - 1 ? "\n" : " "));
        }
    }
}

• Cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

vector<int> distributeLoad(int N, int K, const vector<int>& C, const vector<int>& T) {
    // 检查是否有足够的容量
    long long totalCapacity = 0;
    for (int i = 0; i < K; ++i) {
        totalCapacity += 200LL * C[i] - T[i];
    }
    if (totalCapacity < N) {
        return vector<int>(K, 0);
    }

    // 二分查找合适的负载率
    double left = 0, right = 1.0;
    for (int i = 0; i < K; ++i) {
        left = max(left, static_cast<double>(T[i]) / (200 * C[i]));
    }

    while (right - left > 1e-6) {
        double mid = (left + right) / 2;
        long long allocated = 0;
        for (int i = 0; i < K; ++i) {
            allocated += max(0, static_cast<int>(200 * C[i] * mid) - T[i]);
        }
        if (allocated < N) {
            left = mid;
        } else {
            right = mid;
        }
    }

    // 计算每个节点应该新增的负载数
    vector<int> result(K);
    int sum = 0;
    for (int i = 0; i < K; ++i) {
        result[i] = max(0, static_cast<int>(200 * C[i] * right) - T[i]);
        sum += result[i];
    }

    // 处理可能的舍入误差
    int diff = N - sum;
    for (int i = 0; i < K && diff > 0; ++i) {
        if (result[i] < 200 * C[i] - T[i]) {
            result[i]++;
            diff--;
        }
    }

    return result;
}

int main() {
    int N, K;
    cin >> N >> K;
    vector<int> C(K), T(K);

    for (int i = 0; i < K; ++i) {
        cin >> C[i];
    }
    for (int i = 0; i < K; ++i) {
        cin >> T[i];
    }

    vector<int> result = distributeLoad(N, K, C, T);
    for (int i = 0; i < K; ++i) {
        cout << result[i] << (i == K - 1 ? "\n" : " ");
    }

    return 0;
}

�