华为OD统一考试- 信道分配

题目描述

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

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

1. 所有信道都有属性:”阶”。阶为 r的信道的容量为 2^r比特;
2. 所有用户需要传输的数据量都一样:D比特;
3. 一个用户可以分配多个信道，但每个信道只能分配给一个用户;
4. 只有当分配给一个用户的所有信道的容量和>=D，用户才能传输数据;

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

输入描述

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

0<=R<20

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

0<=i<=R,0<=Ni<1000.

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

0<D<1000000

输出描述

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

用例

题目解析

这题是真的难，可能是我没想到点子上吧，解法想了一晚上，第二天带着两个黑眼圈，灵光一闪，有了下面的解法。

首先，题目的意思，我一开始就没看懂，后面琢磨来琢磨去，分析题目的意思应该是：

第一行输入的r表示第二行的最大阶数，第二行又是r+1个数，也就是说：

比如第一行输入的r=5，则第二行会输入r+1=6个数，如下

• 第一个数10，的阶是0，即容量是2^0的信道有10个
• 第二个数  5，的阶是1，即容量是2^1的信道有5个
• 第三个数  0，的阶是2，即容量是2^2的信道有0个
• 第四个数  1，的阶是3，即容量是2^3的信道有1个
• 第五个数  3，的阶是4，即容量是2^4的信道有3个
• 第六个数  2，的阶是5，即容量是2^5的信道有2个

题目要求从上面给定的多种信道中，任意挑选几个（未使用的）进行组合，让组合之和大于等于第三行输入的D值，问这种组合最多能有多少个？

这题，我一开始想要dfs求得所有无重复使用信道的组合，但是发现只能求出一类，而无法求出多类。大家可以试试，看看dfs行不行。

之后我又想，想要最多的组合情况，那么信道就要省着用，比如每个用户需要至少D容量的信道组合，那么我们就尽可能地构造出容量准确为D的信道组合，

比如 16 + 8 + 4 + 2 = 30，因此我们可以选择：

一个阶4的信道，一个阶3的信道，一个阶2的信道，一个阶1的信道。

但是由于没有阶2的信道，因此我们可以将对于阶2的需求降级，变为两个阶1的信道，也就是说最终选择是：

一个阶4的信道，一个阶3的信道，三个阶1的信道。

即 16 + 8 + 2 * 3 = 30

另外，如果单个信道容量就能满足D，比如阶5的单个信道容量是32，虽然此时浪费了一些，但是一个信道只能给一个用户使用，因此为了避免更大的浪费，32的信道就可以单独组合，而不需要组合其他信道。

那么如何能准确的构造出容量为30的信道组合呢？

题目中信道容量是2^n，因此我有了如下思路：

首先，我们将D值转为二进制，然后转为字符数组，再反序，让D和N的阶数方向保持一致，

比如D=30，可以转为[0, 1, 1, 1, 1] 的反序二进制值的个数数组，该数组的含义是

• 2^0有0个
• 2^1有1个
• 2^2有1个
• 2^3有1个
• 2^4有1个

而输入的第二行，也就是N也可以看成反序二进制数的个数数组： [10, 5, 0, 1, 3, 2]

该数组的含义是：

• 2^0有10个
• 2^1有5个
• 2^2有0个
• 2^3有1个
• 2^4有3个
• 2^5有2个

如果想从N中选几个信道组成和为D的组合，那么不就是N和D的二进制值个数求差吗？

我们只需要比较D.length范围的内，而超出D.length范围的N[i]其实就是单个信道就足以满足一个用户通信的。

如上图所示，如果每次求差后，N[0] >= 0，则表示可以构造出一个和为30的信道组合。

但是N[0] < 0 只能表示无法构造出一个和准确为30的的信道组合，但是却还是有可能构造出一个和大于30的信道组合

程序输入

5

10 5 0 1 3 2

47

对应的N和D如下

 直到N[i]完全抵消了负值结束，然后count++。也可能N[i]到最后也没有抵消完负值，此时说明无法构造出一个和大于30的信道组合，整个程序结束。

以下代码比较难以理解，建议大家debug模式帮助理解，可以监听几个关键值

• N：输入的第二行转化来信道个数数组
• D2：输入的第三行D转化来的构造出准确D容量的信道个数数组
• i：循环变量
• minus：N[i]和D2[i]的差值
• count：满足要求的

上面举得例子

5

10 5 0 1 3 2

47

进行二进制减法时存在问题

如下图所示，在进行第二次减法时

之前的