题目重点：保留 (i,j) 与 (j,i) 及自配对，用单调矩阵堆枚举；大 K 时讨论阈值计数与前缀和。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 唯一性按节点下标，有相同带宽的两个节点仍不同。节点可以参与多个 channel，只禁止重复使用同一个有序下标对。
- 必须选 K 个，0≤K≤n²；代码兼容负值，但实际带宽非负。
- 排序只是重新编号，保留全部 n 个节点，不对带宽值去重。
解题路线
- 排序带宽 b 为降序。所有收益形成 n×n 矩阵 S[i,j]=b_i+b_j，每行每列非递增。左上角是最大候选。
- 用最大堆弹出一个坐标后，将其下方和右方坐标放入堆；visited 按 (i,j) 去重。每个未输出坐标都能从左上角沿非增路径到达，路径上第一处未弹节点处于候选前沿，因此前沿最大值就是全局剩余最大值。
- 弹出 K 次累加。相同和值仍须重复计入不同坐标；visited 不能按和值。此版本适合 K 较小，用于展示正确的枚举语义。
- K 接近 n² 时，堆枚举过慢。对整数阈值 T，用排序双指针统计和值≥T的有序对数与总和；每行满足条件的列是连续前缀，可用带宽前缀和批量求和。二分找到最大的 T 使 count(≥T)≥K，答案为 sum(>T)+(K−count(>T))·T。明确整数值域后才能给二分次数。
手动走一遍
训练例 b=[5,2]，四个有序对收益分别 10、7、7、4；K=3 时答案 24，两个 7 分别来自 (0,1) 与 (1,0)。若错误地只选无序且不自配对，候选只剩 7，会完全改变问题。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from heapq import heappop, heappush
def maximum_data_flow(bandwidth: list[int], stream_count: int) -> int:
"""Choose distinct ordered index pairs, allowing (i, i)."""
n = len(bandwidth)
if stream_count < 0 or stream_count > n * n:
raise ValueError("stream_count must be between 0 and n squared")
if not stream_count:
return 0
ordered = sorted(bandwidth, reverse=True)
heap = [(-(ordered[0] + ordered[0]), 0, 0)]
seen = {(0, 0)}
total = 0
for _ in range(stream_count):
neg_sum, i, j = heappop(heap)
total -= neg_sum
for ni, nj in ((i + 1, j), (i, j + 1)):
if ni < n and nj < n and (ni, nj) not in seen:
seen.add((ni, nj))
heappush(heap, (-(ordered[ni] + ordered[nj]), ni, nj))
return total
复杂度
堆版本 O(n log n+K log(K+1)) 时间、O(n+K) 空间。阈值版本排序后每次统计 O(n)，整体 O(n log n+n log V)，V 为整数和值搜索范围；避免对没有公开的规模承诺堆版本一定能过 OA。
易错点与追问
容易失分的边界
- 误用每台只参与一次的 matching。
- 去掉自配对或把镜像坐标合并。
- 按和值 visited，丢失重复带宽节点。
- 二分统计用 ≥T，却在扣除边界重复项时混用 >T。
继续深挖
- 禁止 (i,i) 时阈值计数如何扣掉对角线？
- 若 (i,j) 与 (j,i) 同一个连接，怎样只计一半？
- 若每个节点有使用次数上限，为什么单调矩阵前 K 不再保证可行？
