> 在正式进入题解前，先说个变动：以后蒟蒻更题解不再在题目直接说明关键步骤
A11.排座椅题解
题目分析
题目要求在 M×NM \times NM×N 的教室中，设置 KKK 条横向通道（行间通道）和 LLL 条纵向通道（列间通道），使得交头接耳的同学对数最少。关键在于：每条通道可以隔开一定数量的交头接耳对。
* 交头接耳的同学必然是相邻的（上下或左右相邻）：
* 上下相邻（同行）：位置 (x1,y)(x_1, y)(x1 ,y) 和 (x2,y)(x_2, y)(x2 ,y)（x1=x2−1x_1 = x_2 - 1x1 =x2 −1），此时在 x1x_1x1 行和 x1+1x_1+1x1 +1 行之间设置横向通道可隔开这对。
* 左右相邻（同列）：位置 (x,y1)(x, y_1)(x,y1 ) 和 (x,y2)(x, y_2)(x,y2 )（y1=y2−1y_1 = y_2 - 1y1 =y2 −1），此时在 y1y_1y1 列和 y1+1y_1+1y1 +1 列之间设置纵向通道可隔开这对。
因此，问题转化为：统计每行/列间能隔开的交头接耳对数，选择价值最大的 KKK 个行间位置和 LLL 个列间位置。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
1. 统计价值：
* 创建数组 row[1..M-1]：row[i] 表示第 iii 行和 i+1i+1i+1 行之间能隔开的交头接耳对数（上下相邻的对）。
* 创建数组 col[1..N-1]：col[j] 表示第 jjj 列和 j+1j+1j+1 列之间能隔开的交头接耳对数（左右相邻的对）。
2. 选择最优通道：
* 将 row 按值从大到小排序（值相同按位置从小到大），取前 KKK 个位置。
* 将 col 按值从大到小排序（值相同按位置从小到大），取前 LLL 个位置。
* 由于题目要求输出位置从小到大，需对选中的位置再排序。
3. 输出结果：
* 第一行输出 KKK 个横向通道位置（从小到大）。
* 第二行输出 LLL 个纵向通道位置（从小到大）。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码实现（可食）
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
复杂度分析
* 时间复杂度：O(D+(M+N)log(M+N))O(D + (M + N) \log (M + N))O(D+(M+N)log(M+N))
* DDD：统计交头接耳对。
* (M+N)log(M+N)(M + N) \log (M + N)(M+N)log(M+N)：排序行/列价值。
* 空间复杂度：O(M+N)O(M + N)O(M+N)
* 存储 row、col 和排序数组。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
正确关键
* 贪心策略：选择能隔开最多交头接耳对的通道，最大化减少交头接耳对数。
* 唯一性保证：题目输入保证最优方案唯一，排序规则（价值大优先，位置小优先）确保输出唯一。
* 边界处理：row 和 col 索引从 1 开始，覆盖 111 到 M−1M-1M−1 和 111 到 N−1N-1N−1。
> 本题本质是最大化被隔开的交头接耳对数，通过统计每行/列间的价值并贪心选择，即可得到最优解。
