题面解释:

小塔有$n$台交换机设备，用于搭建并行计算接入网络。给定两个长度为$n$的整数数组$port$和$bandwidth$，其中$port[i]$表示第$i$台交换机的端口数量，而$bandwidth[i]$表示第$i$台交换机单个端口的带宽。需要从这$n$台交换机中选择最多$k$台不同的交换机，以使网络的总带宽最大化，定义为所选交换机的总端口数量乘以所选交换机中端口带宽的最小值。请你返回最多选择$k$台不同交换机的情况下，网络总带宽的最大值。输入包括交换机数量$n$、端口数量数组$port$、带宽数组$bandwidth$和最多选择的交换机数量$k$，输出为最大总带宽的整数值。

思想

为了最大化网络节点的总带宽，可以采用以下策略：最大化带宽和接口数量的乘积。总带宽的计算公式为：

其中，端口带宽是由所有端口的交换机中最小的端口带宽决定的。因此，优化目标是选择端口带宽最小的交换机，并在这些交换机中选择端口数目最多的前 $k$ 个交换机。

具体方法如下：

1. 确定最小带宽：首先枚举所有交换机，将每个交换机的端口带宽视为最小带宽，并基于这一假设进行计算。
2. 贪心策略：在所有带宽大于当前最小带宽的交换机中，贪心地选择前 $k-1$ 个具有最大端口数的交换机，以最大化端口总数。这样做的理由是，较大的端口数可以显著提高总带宽。
3. 排序选择：对所有交换机按照端口数量从大到小进行排序，然后从排序后的列表中选择前 $k-1$ 个交换机。这种选择策略确保了优先选择具有更多端口的交换机，从而优化总带宽。

通过这种方法，可以有效地在给定数量的交换机中最大化网络的总带宽。

时间复杂度

1. 输入部分：

   • 输入交换机的数量$n$，以及每台交换机的端口数量和带宽。这个步骤的时间复杂度是 $O(n)$，因为我们需要读取每个交换机的两个属性。

2. 排序：

   • 对交换机按照端口数量进行排序，使用了sort函数，时间复杂度为 $O(n \log n)$。

3. 总带宽计算：

   • 外层循环遍历每个交换机（$n$个），内层循环贪心选择满足条件的交换机。最坏情况下，内层循环也可能遍历所有$n$个交换机，因此内层循环的时间复杂度为 $O(n)$。
   • 因此，这一部分的总时间复杂度为 $O(n^2)$，因为我们在外层循环中最多执行 $n$ 次，每次执行内层循环的时间复杂度为 $O(n)$。

代码

python

class PP:
    # 定义交换机类，包含端口数量（num）和端口带宽（wid）
    def __init__(self, num, wid):
        self.num = num
        self.wid = wid

def main():
    # 输入交换机的数量
    n = int(input())

    # 初始化一个空列表 p 来存储每个交换机的端口信息
    p = [None] * (n + 1)

    # 输入每个交换机的端口数目
    num = list(map(int, input().split()))

    # 输入每个交换机的端口带宽
    width = list(map(int, input().split()))

    # 将每个交换机的端口数目和带宽封装成 PP 对象，并存储到列表 p 中
    for i in range(1, n + 1):
        p[i] = PP(num[i-1], width[i-1])

    # 输入要选择的交换机数量 k
    k = int(input())

    # 按照端口数从大到小排序交换机
    p = sorted(p[1:], key=lambda x: x.num, reverse=True)

    # 初始化最大带宽乘积为 0
    ans = 0

    # 遍历每个交换机，假设其端口带宽为最小带宽
    for i in range(n):
        # 当前交换机的端口数作为基础值
        sum_num = p[i].num
        cnt = 1  # 已选择的交换机数量

        # 遍历剩余交换机，选择符合条件的交换机
        for j in range(n):
            # 如果当前交换机的带宽大于等于基准交换机带宽，且不重复选择相同的交换机
            if p[j].wid >= p[i].wid and j != i:
                sum_num += p[j].num  # 累加端口数
                cnt += 1  # 更新已选择交换机的数量

            # 如果已选择了 k 个交换机，则停止选择
            if cnt == k:
                break

        # 计算当前组合的带宽乘积，并更新最大值
        ans = max(ans, sum_num * p[i].wid)

    # 输出最大带宽乘积
    print(ans)

if __name__ == "__main__":
    main()

c++

#include <bits/stdc++.h>
using namespace std;

// 定义交换机结构体，包含端口数量（num）和端口带宽（wid）
struct pp {
    int num;  // 端口数量
    int wid;  // 端口带宽
} p[105];  // 存储最多 105 个交换机的信息

int main() {
    int n;
    // 输入交换机的数量
    cin >> n;

    // 输入每个交换机的端口数目
    for (int i = 1; i <= n; i++)
        cin >> p[i].num;

    // 输入每个交换机的端口带宽
    for (int i = 1; i <= n; i++)
        cin >> p[i].wid;

    // 输入需要选择的交换机数量 k
    int k;
    cin >> k;

    // 按照端口数量从大到小对交换机进行排序
    sort(p + 1, p + n + 1, [&](pp a, pp b) {
        return a.num > b.num;  // 比较端口数量
    });

    // 初始化最大带宽乘积为 0
    int ans = 0;

    // 遍历每个交换机，假设其端口带宽为当前最小带宽
    for (int i = 1; i <= n; i++) {
        int sum = p[i].num;  // 当前交换机的端口数作为基础值
        int cnt = 1;  // 已选择的交换机数量初始为 1，包含当前交换机

        // 贪心选择带宽满足条件的交换机
        for (int j = 1; j <= n && cnt < k; j++) {
            // 选择带宽大于等于当前交换机的带宽，且不重复选择相同的交换机
            if (p[j].wid >= p[i].wid && j != i) {
                sum += p[j].num;  // 累加满足条件的交换机的端口数
                cnt++;  // 更新已选择的交换机数量
            }
        }

        // 更新最大带宽乘积
        ans = max(ans, sum * p[i].wid);  // 计算当前假设的总带宽，并更新最大值
    }

    // 输出最大带宽乘积
    cout << ans << endl;

    return 0;
}

java

import java.util.*;

// 定义交换机类，包含端口数量（num）和端口带宽（wid）
class PP {
    int num;
    int wid;

    PP(int num, int wid) {
        this.num = num;
        this.wid = wid;
    }
}

public class MaximizeBandwidth {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 输入交换机的数量
        int n = sc.nextInt();
        sc.nextLine();  // 处理换行符

        // 输入每个交换机的端口数目
        int[] num = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        // 输入每个交换机的端口带宽
        int[] width = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        // 创建交换机数组
        PP[] p = new PP[n + 1];
        for (int i = 1; i <= n; i++) {
            p[i] = new PP(num[i - 1], width[i - 1]);
        }

        // 输入要选择的交换机数量 k
        int k = sc.nextInt();

        // 按照端口数量从大到小对交换机进行排序
        Arrays.sort(p, 1, n + 1, (a, b) -> Integer.compare(b.num, a.num));

        // 初始化最大带宽乘积为 0
        int ans = 0;

        // 遍历每个交换机，假设其端口带宽为最小带宽
        for (int i = 1; i <= n; i++) {
            int sumNum = p[i].num;  // 当前交换机的端口数作为基础值
            int cnt = 1;  // 已选择的交换机数量

            // 贪心选择带宽满足条件的交换机
            for (int j = 1; j <= n && cnt < k; j++) {
                // 选择带宽大于等于基准交换机带宽，且不重复选择相同的交换机
                if (p[j].wid >= p[i].wid && j != i) {
                    sumNum += p[j].num;  // 累加端口数
                    cnt++;  // 更新已选择的交换机数量
                }
            }

            // 更新最大带宽乘积
            ans = Math.max(ans, sumNum * p[i].wid);
        }

        // 输出最大带宽乘积
        System.out.println(ans);
        sc.close();
    }
}

题目内容

小明有$n$台交换机设备，用于搭建并行计算接入网络，给定长度为$n$的两个整数数组$port$和$bandwidth$，$port$[$i$]代表第$i$台交换机的端口数量,$bandwidth$[$i$]表示$i$台交换机单个端口的带宽(假设同一台交换机设备上各个端口的带宽相同)，需要从这 $n$ 台交换机中选择最多$k$台(可以小于$k$)不同的交换机，使其组成的网络总带宽最大，整个网络总带宽定义为所选交换机的总端口数量乘以所选交换机中端口带宽的最小值，请你返回最多$k$台不同交换机的网络总带宽的最大值。

输入描述

• 第一行的输入是一个整数$n$，表示交换机的数量 $1≤n≤100$
• 第二行的输入是一个长度为$n$的整数数组$port$，表示$n$台交换机的端口数量， $port[i]$表示第$i$台交换机的端口数量,$20≤port[i]≤100$
• 第三行的输入是一个长度为$n$的整数数组$bandwidth$，表示$n$台交换机的端口带宽，$bandwidth[i]$代表第i台交换机的端口带宽$10 ≤bandwidth[i]≤100$
• 第四行的输入是一个整数$k$，表示最多选择的不同交换机数量，$1≤k≤n$

输出描述

一个整数，即最多k台交换机的网络总带宽最大值

样例1

输入

 6
 20 100 30 10 50 80
 50 40 30 90 70 20
 2

输出

6000

说明

从$6$台交换机设备中最多选出$2$台交换机，选择下标为$1$(端口数量为：$100$，带宽为：$40)、下标为$4$(端口数量为：$50$，带宽为：$70$)的两台交换机，则总带宽为最大$(100+50)*min(40,70)=6000$

样例2

输入

5
100 20 50 50 80
100 10 20 20 20
3

输出

10000

说明

此时我们选择下标为$0$的交换机，得到最大的总带宽为$100*100=10000$