题解

题面描述

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

请返回最多 $k$ 台不同交换机的网络总带宽的最大值。

思路

思路总结

为了最大化网络总带宽，我们首先将所有交换机按带宽从高到低排序。然后，遍历排序后的交换机列表，使用一个最小堆（优先队列）来维护当前选中的最多 $k$ 台交换机的端口数量总和。在遍历过程中，每选取一台带宽较高的交换机，将其端口数量加入堆中，并在堆超过 $k$ 台时移除端口最少的交换机，以保证选中的交换机总数不超过 $k$。每次更新时，计算当前选中交换机的端口总和与当前最小带宽的乘积，并记录下最大的值。通过这种贪心策略结合优先队列的方式，能够高效地找到使网络总带宽最大的交换机组合。

具体步骤如下：

1. 排序：将交换机按照带宽从高到低排序。
2. 贪心选择：遍历每一个可能的最小带宽值（即排序后的每一个带宽），在当前带宽及以上的交换机中选择端口数量最多的前 $k$ 台。
3. 计算带宽：对于每一个选择，计算 $(\text{选中交换机的端口总和}) \times (\text{当前带宽})$，并记录最大值。

由于 $n$ 最大为 $100$，可以使用优先队列（最小堆）来维护当前选择的 $k$ 个端口数量，确保每次选择的端口总和是最大的。

cpp

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

// 定义交换机结构体，包含端口数量和带宽
struct Switch {
    int port;       // 端口数量
    int bandwidth;  // 单个端口的带宽
};

int main(){
    int n;
    // 输入交换机的数量
    cin >> n;
    
    vector<int> port(n);
    // 输入每台交换机的端口数量
    for(auto &x : port) cin >> x;
    
    vector<int> bandwidth(n);
    // 输入每台交换机的端口带宽
    for(auto &x : bandwidth) cin >> x;
    
    int k;
    // 输入最多选择的交换机数量
    cin >> k;

    // 创建交换机列表，将端口数量和带宽对应起来
    vector<Switch> switches(n);
    for(int i = 0; i < n; i++){
        switches[i].port = port[i];
        switches[i].bandwidth = bandwidth[i];
    }

    // 按带宽从高到低排序，如果带宽相同，则按端口数量从高到低排序
    sort(switches.begin(), switches.end(), [&](const Switch &a, const Switch &b) -> bool{
        if(a.bandwidth != b.bandwidth) return a.bandwidth > b.bandwidth;
        return a.port > b.port;
    });

    long long max_total = 0;   // 用于记录最大总带宽
    long long sum_ports = 0;   // 当前选中交换机的端口总和
    // 使用最小堆（优先队列）来维护当前选中的交换机端口数量
    priority_queue<int, vector<int>, std::greater<int>> pq;

    // 遍历排序后的交换机列表
    for(int i = 0; i < n; i++){
        sum_ports += switches[i].port;   // 累加当前交换机的端口数量
        pq.push(switches[i].port);       // 将当前交换机的端口数量加入堆中
        
        // 如果选中的交换机数量超过k，移除端口最少的交换机
        if(pq.size() > k){
            sum_ports -= pq.top();       // 减去被移除交换机的端口数量
            pq.pop();                     // 移除堆顶元素
        }
        
        // 计算当前组合的总带宽：(端口总和) * (当前交换机的带宽)
        long long current_total = sum_ports * (long long)switches[i].bandwidth;
        // 更新最大总带宽
        if(current_total > max_total){
            max_total = current_total;
        }
    }

    // 输出最大总带宽
    cout << max_total;
}

python

import sys
import heapq

def main():
    # 读取交换机的数量
    n = int(sys.stdin.readline())
    # 读取每台交换机的端口数量
    port = list(map(int, sys.stdin.readline().split()))
    # 读取每台交换机的端口带宽
    bandwidth = list(map(int, sys.stdin.readline().split()))
    # 读取最多选择的交换机数量
    k = int(sys.stdin.readline())

    # 创建交换机列表，包含端口数量和带宽
    switches = list(zip(port, bandwidth))
    # 按带宽从高到低排序，如果带宽相同，则按端口数量从高到低排序
    switches.sort(key=lambda x: (-x[1], -x[0]))

    max_total = 0      # 用于记录最大总带宽
    sum_ports = 0      # 当前选中交换机的端口总和
    min_heap = []      # 最小堆，用于维护当前选中的交换机端口数量

    # 遍历排序后的交换机列表
    for p, b in switches:
        sum_ports += p               # 累加当前交换机的端口数量
        heapq.heappush(min_heap, p) # 将当前交换机的端口数量加入堆中
        
        # 如果选中的交换机数量超过k，移除端口最少的交换机
        if len(min_heap) > k:
            sum_ports -= heapq.heappop(min_heap)  # 减去被移除交换机的端口数量
        
        # 计算当前组合的总带宽：(端口总和) * (当前交换机的带宽)
        current_total = sum_ports * b
        # 更新最大总带宽
        if current_total > max_total:
            max_total = current_total

    # 输出最大总带宽
    print(max_total)

if __name__ == "__main__":
    main()

java

import java.util.*;
import java.io.*;

public class Main {
    // 定义交换机类，包含端口数量和带宽
    static class Switch {
        int port;        // 端口数量
        int bandwidth;   // 单个端口的带宽

        Switch(int port, int bandwidth){
            this.port = port;
            this.bandwidth = bandwidth;
        }
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        // 读取交换机的数量
        int n = Integer.parseInt(br.readLine());
        
        // 读取每台交换机的端口数量
        String[] portStr = br.readLine().split(" ");
        // 读取每台交换机的端口带宽
        String[] bandwidthStr = br.readLine().split(" ");
        
        // 读取最多选择的交换机数量
        int k = Integer.parseInt(br.readLine());

        // 创建交换机列表，包含端口数量和带宽
        List<Switch> switches = new ArrayList<>();
        for(int i = 0; i < n; i++){
            switches.add(new Switch(Integer.parseInt(portStr[i]), Integer.parseInt(bandwidthStr[i])));
        }

        // 按带宽从高到低排序，如果带宽相同，则按端口数量从高到低排序
        switches.sort((a, b) -> {
            if(b.bandwidth != a.bandwidth){
                return b.bandwidth - a.bandwidth;
            }
            return b.port - a.port;
        });

        long max_total = 0;    // 用于记录最大总带宽
        long sum_ports = 0;    // 当前选中交换机的端口总和
        // 使用最小堆（优先队列）来维护当前选中的交换机端口数量
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        // 遍历排序后的交换机列表
        for(Switch sw : switches){
            sum_ports += sw.port;    // 累加当前交换机的端口数量
            pq.offer(sw.port);        // 将当前交换机的端口数量加入堆中
            
            // 如果选中的交换机数量超过k，移除端口最少的交换机
            if(pq.size() > k){
                sum_ports -= pq.poll();  // 减去被移除交换机的端口数量
            }
            
            // 计算当前组合的总带宽：(端口总和) * (当前交换机的带宽)
            long current_total = sum_ports * (long)sw.bandwidth;
            // 更新最大总带宽
            if(current_total > max_total){
                max_total = current_total;
            }
        }

        // 输出最大总带宽
        System.out.println(max_total);
    }
}

题目内容

有 $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$