题面解释:

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

思想

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

\text{总带宽} = \text{端口带宽} \times \sum \text{端口数目}

P2305.第3题-小明的交换机

1000ms

Tried: 352

Accepted: 120

Difficulty: 5

所属公司 : 华为

算法与标签>贪心算法

题目内容

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

输出

说明

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

输出

说明

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

输入

预期输出（选填）

题面解释:

思想

P2305.第3题-小明的交换机

题目内容

输入描述

输出描述

样例1

样例2

Status

Development

Support

About