HJ171. 排座椅
题目描述
教室 M 行 N 列，需设置 K 条横向通道和 L 条纵向通道。有 D 对相邻的同学常交头接耳。放置通道后，希望被通道隔开的交头接耳对尽可能多（即未被隔开的对最少）。输出唯一最优方案：第一行 K 个横向通道位置（行号，递增），第二行 L 个纵向通道位置（列号，递增）。
输入格式
- 第 1 行：M、N、K、L、D
- 接下来 D 行：每行 4 个整数，表示相邻的两对坐标
输出格式
- 第 1 行：K 个行号（递增）
- 第 2 行：L 个列号（递增）
示例
示例 1
输入：
4 5 1 2 3
4 2 4 3
2 3 3 3
2 5 2 4
输出：
2
2 4
说明： 教室 4 行 5 列，设 1 条横向通道和 2 条纵向通道，能隔开尽可能多的交头接耳对。
解题思路
第一步：理解问题本质
一条横向通道（位于第 x 行与第 x+1 行之间）能隔开"上下相邻"的交头接耳对（行号分别为 x、x+1）；一条纵向通道同理隔开"左右相邻"对。目标是让选出的通道隔开尽可能多的对。
第二步：暴力解法（枚举通道组合）
枚举所有 K 条横向 + L 条纵向通道的组合，计算每种组合能隔开的对数，取最大者。
问题：组合数爆炸，M、N、D 较大时无法枚举。
第三步：优化解法（贪心）
每对相邻同学只可能被一条特定的通道隔开：
- 若行号相同（左右相邻），只能被列号较小那条纵向通道隔开
- 若列号相同（上下相邻），只能被行号较小那条横向通道隔开
因此只需统计每条候选通道能隔开的对数，贪心选取隔开对数最多的前 K 条横向、前 L 条纵向通道即可。
第四步：最优解法
分别统计 row_cnt[x]（第 x 行下放横向通道隔开的对数）和 col_cnt[y]（第 y 列右放纵向通道隔开的对数），排序选前 K / L，最后递增输出：
rows = sorted(range(1, M), key=lambda x: row_cnt[x], reverse=True)[:K]
cols = sorted(range(1, N), key=lambda y: col_cnt[y], reverse=True)[:L]
print(' '.join(map(str, sorted(rows))))
print(' '.join(map(str, sorted(cols))))
题目保证最优方案唯一，因此不需要额外处理并列。
完整代码实现
算法可视化 · 逐帧回放这道题的代码26 帧 · 录制输入
import sys
def solve() -> None:
data = sys.stdin.buffer.read().split()
it = iter(data)
M, N, K, L, D = int(next(it)), int(next(it)), int(next(it)), int(next(it)), int(next(it))
row_cnt = [0] * (M + 1) # row_cnt[x]：在第 x 与 x+1 行之间设通道能隔开的对数
col_cnt = [0] * (N + 1) # col_cnt[y]：在第 y 与 y+1 列之间设通道能隔开的对数
for _ in range(D):
x1, y1, x2, y2 = int(next(it)), int(next(it)), int(next(it)), int(next(it))
if x1 == x2: # 左右相邻，用纵向通道隔开
col_cnt[min(y1, y2)] += 1
else: # 上下相邻，用横向通道隔开
row_cnt[min(x1, x2)] += 1
# 贪心：选能隔开对数最多的 K 条横向通道
rows = sorted(range(1, M), key=lambda x: row_cnt[x], reverse=True)[:K]
cols = sorted(range(1, N), key=lambda y: col_cnt[y], reverse=True)[:L]
print(' '.join(map(str, sorted(rows))))
print(' '.join(map(str, sorted(cols))))
if __name__ == "__main__":
solve()
示例推演
以示例 1 为例，M=4、N=5、K=1、L=2、D=3。
三条交头接耳对：
(4,2)与(4,3)：行号相同 → 左右相邻，col_cnt[min(2,3)] = col_cnt[2] += 1(2,3)与(3,3)：列号相同 → 上下相邻，row_cnt[min(2,3)] = row_cnt[2] += 1(2,5)与(2,4)：行号相同 → 左右相邻，col_cnt[min(5,4)] = col_cnt[4] += 1
统计结果：
row_cnt[2] = 1，其余横向候选为 0col_cnt[2] = 1，col_cnt[4] = 1，其余纵向候选为 0
选取 K=1 条横向（隔开最多为 row_cnt[2]）：rows = [2]
选取 L=2 条纵向（col_cnt[2]、col_cnt[4]）：cols = [2, 4]
递增输出：
2
2 4
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 枚举组合 | O(C(M,K)·C(N,L)·D) | O(1) | 组合爆炸，不可行 |
| 贪心计数 | O(D + (M+N)·log(M+N)) | O(M+N) | 统计 + 排序 |
M、N 为行数列数，D 为交头接耳对数
易错点总结
1. 通道隔开的是"对"而不是"同学"
一条通道能隔开多对相邻同学，统计时每对同学对计数 +1，而不是每个同学。
2. 上下/左右判断反了
行号相同是左右相邻（用纵向通道），列号相同是上下相邻（用横向通道），判断条件 x1==x2 和取 min 不能搞混。
3. 输出必须递增
贪心选出的通道可能无序，输出前必须 sorted()，否则不满足"递增"要求。
扩展思考
- 贪心正确性依赖"每条通道隔开对数互不影响"，本题每对同学只可能被唯一一条通道隔开，因此贪心成立。
- 若需保证隔开对数的同时方案不唯一，题目会要求输出任一或特殊规则，需额外处理。