华为OD机试 - 信道分配 - 贪心算法（Java 2024 D卷 200分）

在这里插入图片描述

华为OD机试 2024D卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试（JAVA）真题（D卷+C卷+A卷+B卷）》。

刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

算法工程师Q小明面对着这样一个问题，需要将通信用的信道分配给尽量多的用户：

信道的条件及分配规则如下：

所有信道都有属性"阶"。阶为r的信道的容量为 2^r 比特；
所有用户需要传输的数据量都一样：D比特；
一个用户可以分配多个信道，但每个信道只能分配给一个用户；
当且仅当分配给一个用户的所有信道的容量和 >= D，用户才能传输数据；

给出一组信道资源，最多可以为多少用户传输数据？

二、输入描述

第一行，一个数字 R。R为最大阶数。

0 <= R < 20

第二行，R+1个数字，用空格隔开。代表每种信道的数量 Ni。按照阶的值从小到大排列。

0 <= i <= R，0 <= Ni < 1000

第三行，一个数字 D。D为单个用户需要传输的数据量。

0 < D < 1000000

三、输出描述

一个数字（代表最多可以供多少用户传输数据）

四、测试用例

测试用例1：

1、输入

5
10 5 0 1 3 2
30

2、输出

3、说明

这个用例中，最大阶数为5，信道的数量分别为10, 5, 0, 1, 3, 2，每个用户需要传输30比特的数据。以下是信道的容量及分布：

2^0: 10个
2^1: 5个
2^2: 0个
2^3: 1个
2^4: 3个
2^5: 2个

30的二进制表示为11110，所需的最小信道组合是：

2^4: 1个 (16)
2^3: 1个 (8)
2^2: 0个 (0)
2^1: 1个 (4)
2^0: 0个 (0)

这样可以满足5个用户的传输需求。

测试用例2：

1、输入

3
2 2 1 0
7

2、输出

3、说明

这个用例中，最大阶数为3，信道的数量分别为2, 2, 1, 0，每个用户需要传输7比特的数据。以下是信道的容量及分布：

2^0: 2个
2^1: 2个
2^2: 1个
2^3: 0个

7的二进制表示为111，所需的最小信道组合是：

2^2: 1个 (4)
2^1: 1个 (2)
2^0: 1个 (1)

这样可以满足1个用户的传输需求。

五、解题思路

1、贪心算法

采用贪心算法的主要原因是该算法可以在每一步都选择当前最优解，从而高效地找到全局最优解或接近最优的解。

2、为什么采用？

（1）问题特点

信道容量和用户需求的多样性：信道的容量是按照阶数的幂次递增的，而用户的需求是固定的，这意味着高阶信道可以提供更大的容量，因此优先使用高阶信道可以更快满足用户需求。

问题规模和复杂性：信道的数量和种类相对较多，如果采用其他如动态规划的方法可能会增加时间和空间复杂度，而贪心算法相对简单且高效，能够在较短时间内完成分配。

（2）贪心算法的具体应用

优先使用大容量信道：在每一步中，尽量优先使用容量最大的信道来满足用户需求，这样可以尽可能减少需要使用的信道数量，从而更高效地利用资源。

逐步减少需求：通过逐步减少用户的需求量，使得剩余的需求能够被更小的信道满足，直到完全满足用户需求。

（3）具体实现

将需求量转换为二进制：将用户的需求量转换为二进制表示，方便逐位进行处理，从高阶位到低阶位逐步满足需求。
逐位处理需求：对于每一位，优先使用当前位能够满足的信道数量，若不足则向更低位借用，逐步减少需求量。
迭代处理每个用户：通过迭代不断尝试满足更多用户的需求，直到不能再满足新的用户为止。

3、具体步骤：

我们需要分配信道来满足尽量多的用户数据传输需求。每个用户的数据需求量是固定的，我们可以使用多个信道来满足一个用户的需求，但每个信道只能分配给一个用户。信道的容量由其阶数决定，阶数为 r 的信道容量为 2^r 比特。

输入读取与处理
- 读取最大阶数 r。
- 读取每种阶数信道的数量，存储在数组 channelCounts 中。
- 读取每个用户需要传输的数据量 requiredData。
将 requiredData 转换为二进制表示
- 将 requiredData 转换为二进制表示，并将其逆序存储在列表 binaryData 中。这样方便从低位到高位处理。
初始处理多余的信道
- 如果 channelCounts 数组长度大于 binaryData 数组长度，将多余的信道数量直接累加到用户计数 userCount 中，因为这些多余的高阶信道可以直接满足用户需求。
贪心算法分配信道
- 复制 binaryData 列表到 tempData，用于当前迭代的处理。
- 从高阶信道到低阶信道遍历，对于每个信道：
- 计算当前信道数量 channelCounts[i] 和所需信道数量 tempData[i] 之间的差异 diff。
- 如果 diff >= 0，则当前信道数量足够满足需求，更新信道数量，并将所需信道数量置为0。
- 如果 diff < 0，则当前信道数量不足，需要向低阶信道借用，更新低阶信道的需求量。
- 处理完所有信道后，检查 channelCounts[0] 是否足够满足 tempData[0] 的需求，如果满足，则增加用户计数 userCount，否则尝试升位处理。
- 如果在升位过程中发现无法满足需求，则退出循环。
返回结果
- 返回能够满足传输需求的最大用户数 userCount。

六、Java算法源码

public class OdTest {public static void main(String[] args) {Scanner sc = new Scanner(System.in);// 获取输入数据int maxLevel = sc.nextInt();int[] channelCounts = new int[maxLevel + 1];for (int i = 0; i <= maxLevel; i++) {channelCounts[i] = sc.nextInt();}int requiredData = sc.nextInt();// 计算并输出结果System.out.println(calculateMaxUsers(maxLevel, channelCounts, requiredData));}// 计算最多可以为多少用户传输数据public static int calculateMaxUsers(int maxLevel, int[] channelCounts, int requiredData) {// 将 requiredData 转换为二进制，并逆序存储在列表中List<Integer> binaryData = new ArrayList<>();while (requiredData > 0) {binaryData.add(requiredData % 2);requiredData /= 2;}int userCount = 0;// 如果 channelCounts 数组长度大于 binaryData 数组长度，直接将多余的 channelCounts[i] 累加到 userCountif (channelCounts.length > binaryData.size()) {for (int i = binaryData.size(); i < channelCounts.length; i++) {userCount += channelCounts[i];}}// 贪心算法，尽量用大的信道先满足用户需求while (true) {List<Integer> tempData = new ArrayList<>(binaryData); // 复制一份 binaryData 列表for (int i = binaryData.size() - 1; i > 0; i--) {if (channelCounts[i] > 0) {int diff = channelCounts[i] - tempData.get(i); // 求当前位置的差异if (diff >= 0) {channelCounts[i] = diff; // 更新 channelCounts[i]，相当于用掉了当前个数然后剩余的。tempData.set(i, 0); // 当前位要置零} else {tempData.set(i, 0); // 就要向其他位借了。tempData.set(i - 1, tempData.get(i - 1) + Math.abs(diff) * 2); // 降低一位，相当于乘以2。channelCounts[i] = 0; // channelCounts[i] 已经被减去了，所以置为0。}} else { // channelCounts[i] = 0tempData.set(i - 1, tempData.get(i - 1) + tempData.get(i) * 2); // 降位来匹配tempData.set(i, 0); // 降位之后原来的位置要置0}}boolean needToBreak = false; // 标记是否需要退出循环if (channelCounts[0] >= tempData.get(0)) { // 最终第0位承担了所有channelCounts[0] -= tempData.get(0);userCount += 1;} else {channelCounts[0] -= tempData.get(0);tempData.set(0, 0); // 因为 channelCounts[0] -= tempData[0] 的逻辑for (int i = 0; i < binaryData.size(); i++) {if (channelCounts[i] < 0) { // 小于0的要准备升位if (i != binaryData.size() - 1) {channelCounts[i + 1] += channelCounts[i] >> 1;channelCounts[i] = 0;} else {needToBreak = true;}} else {userCount += 1;break;}}}if (needToBreak) {break;}}return userCount;}
}