N = int(input())
K = int(input())
C = list(map(int,input().split()))
T = list(map(int,input().split()))
T_max = []
T_can = []
res = [0]*K 
sum_res = 0
for i in range(K):
    T_max.append(C[i]*200)
    T_can.append(C[i]*200-T[i])
if sum(T_can)<N:
    print(' '.join(str(number) for number in res))
else:
    rate = (N+sum(T))/sum(T_max)
    for i in range(K):
        res[i] = round(rate*T_max[i]-T[i])
    print(' '.join(str(number) for number in res))  

题解思路

本题要求将宕机节点的负载均匀分配给其他节点，以确保各个节点的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会员可以通过点击题目上方《已通过》查看其他通过代码来学习。

n = eval(input())
k = eval(input())
c = list(map(int, input().split()))
t = list(map(int, input().split()))

num_nodes = sum(c) * 200
cur_nodes = sum(t)
if n + cur_nodes > num_nodes:
    res = [0] * k
else:
    r = (n + cur_nodes) / num_nodes
    res = [0] * k
    for i in range(k):
        tmp = c[i] * 200  * r - t[i]
        res[i] = int(tmp + 0.5)
    
for i,num in enumerate(res):
    if i == len(res) - 1:
        print(num, end = "")
    else:
        print(num, end = " ") 

直接计算就通过了。。

# 输入
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:
    min_ratio = 0
    max_ratio = 1
    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=" ")

不用枚举，直接计算可以得到答案：

N = int(input())
K = int(input())
c_list  = list(map(int,input().split()))
t_list = list(map(int,input().split()))
n = len(c_list)
avg_list = [t_list[i]/c_list[i] for i in range(n)]

total = sum(t_list)
target_avg = (sum(t_list)+N)/sum(c_list)

if target_avg>200 or sum([each>target_avg for each in avg_list])>0:
    print(" ".join(map(str,[0] * n)))
else:
    results = [0]*len(c_list)
    for i in range(n):
        results[i] = int(round(target_avg*c_list[i]- t_list[i],0))
    proc_avg = [(t_list[i]+results[i])/c_list[i] for i in range(n)]
    if sum([abs(each-target_avg)>0.0001 for each in proc_avg])>0:
        print(" ".join(map(str, [0] * n)))
    else:
        print(" ".join(map(str, results)))

如果不用枚举，可以解决这个问题吗？ 我这个代码只能过9个用例，还有3个过不了，不知道如何去修改

import java.util.*;
import java.math.*;

public class Main{

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

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

            int[] T = new int[K];
            for(int i = 0; i < K; i++){
                T[i] = in.nextInt();
            }
            computing(N, K, C, T);
        }
    }

    private static void computing(int N, int K, int[] C, int[] T){

        int TSum = N;
        for(int i = 0; i < T.length; i++){
            TSum = TSum + T[i];
        }
        int CSum = 0;
        for(int i = 0; i < C.length; i++){
            CSum = CSum + C[i];
        }

        int[] res = new int[K];
        if(TSum < CSum * 200){
            for(int i = 0; i < K; i++){
                BigDecimal result = new BigDecimal(C[i]).multiply(new BigDecimal(TSum))
                        .divide(new BigDecimal(CSum), 3, RoundingMode.HALF_UP)
                        .subtract(new BigDecimal(T[i]));
                if(result.compareTo(BigDecimal.ZERO) >= 0){
                    res[i] = result.intValue();
                }
            }
        }
        for(int i = 0 ; i < K - 1; i++){
            System.out.print(res[i] + " ");
        }
        System.out.print(res[K - 1]);
    }
}

#include <iostream>
#include <ostream>
#include <string>
#include <vector>
#include<bits/stdc++.h>

typedef long long LL;

using namespace std;


int main() {
    int n,k;
    cin>>n>>k;
    vector<int> c(k);
    vector<int> t(k);
    int sum_c=0;
    int sum_t=0;
    for (int i=0; i<k; i++) {
        cin>>c[i];
        sum_c+=c[i]*200;
    }
    for (int i=0; i<k; i++) {
        cin>>t[i];
        sum_t+=t[i];
    }
    if (n>sum_c-sum_t) {//如果宕机节点的负载数超出了所有节点总负载数，不进行重新调度
        for (int i=0; i<k-1; i++) {
           cout<<0<<" ";
        }
        cout<<0<<endl;
    }
    vector<int>  num(k);//每个节点应该新增的负载数。
    bool fenpei=false;
    for (double i=0.001; i<=1.0; i+=0.001) { //直接枚举0.001-1，使用double可以过，floa不可以
        //即分配后各个计算节点的CPU负载保持相等，精度不低于0.001。
        int sum=0;
        for (int j=0; j<k; j++) {
            num[j]=(int)(i* 200 *c[j]-t[j]);
            sum+=num[j];
        }
        if (sum==n) {
            fenpei=true; //分配成功
            break;
        }
    }
    if (fenpei) {
        for (int i=0; i<k-1; i++) {
           cout<<num[i]<<" ";
        }
        cout<<num[k-1]<<endl;
    
    }else {
      for (int i=0; i<k-1; i++) {
           cout<<0<<" ";
        }
        cout<<0<<endl;
    }
}