刷题笔记合集🔗

信道分配

问题描述

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

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

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

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

输入格式

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

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

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

输出格式

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

样例输入

5
10 5 0 1 3 2
30

样例输出

4

数据范围

• （最大阶数）
• （每种信道的数量）
• （单个用户需要传输的数据量）

题解

先把问题再说一遍：我们有不同“阶”的信道，阶为 r 的容量是 2^r 比特，每种信道有 N_r 根。每个用户要传输 D 比特，可以分配多根信道，只要总容量 ≥ D，就能满足这个用户。

要问“最多能满足多少用户”，直觉上可以枚举用户数 K，然后验证能不能把信道分给这 K 个人。再用二分法在可能的 K 范围里快速找答案。验证“能否满足 K” 的关键，是一种贪心策略：

1. 二分法猜答案

   • 我们先猜一个 K （范围从 0 到所有信道总根数）。
   • 如果能分配给 K 个人，每人凑够 D；就把二分区间往右推（尝试更多用户）。
   • 否则往左推。

2. “能否满足 K” 的贪心验证

   • 用一个大顶堆（优先队列）存放 K 个“还差多少比特没满足”的需求，初始值全都是 D。
   • 从最大阶开始（容量最大的信道）一根根拿出来，分给堆顶那个“最缺”的人，用它减去相应容量，再把新的“剩余需求”放回堆。
   • 如果所有信道用完前，堆里所有需求都被降到 0 或更小（堆空了），说明这 K 个人都能满足；否则 K 太大，不行。

3. 为什么贪心有效

   • 大容量优先补“大缺口”，能最快地凑齐 D。
   • 不会出现“把大块浪费到只差一点的人身上”的情况——因为堆里永远是最大需求优先被补。

4. 举例说明
   以样例

   R=5  
   N=[10,5,0,1,3,2]   // 阶 0 到 5 的信道数  
   D=30
   

   信道总根数 10+5+0+1+3+2=21，所以我们二分的区间是 [0,21]。

   • 试 K=4：堆里4个数都是30。
     • 用两根阶5（容量32）分给两个人，他们的“剩余需求”变为 ≤0，堆里剩下2个30。
     • 再用3根阶4（16），两次给剩余的30减16，变成14，还剩一根16，又给14变成 ≤0。
     • 其实只要一路用下去，很快堆就空了，说明4人都能满足。
   • 试 K=5：到最后信道不够凑齐5个需求，就失败。
     二分后我们得到最大 K=4。

5. 关键技巧

   • 二分答案：把“求最大 K” 转成 “能／不能” 的判定问题。
   • 优先队列 + 贪心：保证每次用容量最大的信道去补当前“最缺” 的需求。

6. 复杂度分析

   • 信道总根数最多 < 20×1000=20000。
   • 二分 步，每步做一次“遍历所有信道+堆操作”，共，约几千万次操作，C++/Java/Python 都能承受。

7. 其他思路

   • 理论上也能建网络流模型求最大匹配，但写起来麻烦。这种“二分+贪心”更直观、代码量少，上手快。

参考代码

• Python

import sys
import heapq

def can_serve(K, R, Ns, D):
    # K=0 肯定能满足
    if K == 0:
        return True
    # 大顶堆存放还差多少比特
    pq = [-D] * K
    heapq.heapify(pq)
    # 从高阶到低阶用信道
    for r in range(R, -1, -1):
        cap = 1 << r
        for _ in range(Ns[r]):
            if not pq:
                return True
            need = -heapq.heappop(pq)
            # 用一根信道补贴 need
            need -= cap