在正式进入题解前，先说个变动：以后蒟蒻更题解不再在题目直接说明关键步骤

A11.排座椅题解

题目分析

题目要求在 $M \times N$ 的教室中，设置 $K$ 条横向通道（行间通道）和 $L$ 条纵向通道（列间通道），使得交头接耳的同学对数最少。关键在于：每条通道可以隔开一定数量的交头接耳对。

• 交头接耳的同学必然是相邻的（上下或左右相邻）：
  • 上下相邻（同行）：位置 $(x_1, y)$ 和 $(x_2, y)$（$x_1 = x_2 - 1$），此时在 $x_1$ 行和 $x_1+1$ 行之间设置横向通道可隔开这对。
  • 左右相邻（同列）：位置 $(x, y_1)$ 和 $(x, y_2)$（$y_1 = y_2 - 1$），此时在 $y_1$ 列和 $y_1+1$ 列之间设置纵向通道可隔开这对。

因此，问题转化为：统计每行/列间能隔开的交头接耳对数，选择价值最大的 $K$ 个行间位置和 $L$ 个列间位置。

---

解题思路

1. 统计价值：

   • 创建数组 row[1..M-1]：row[i] 表示第 $i$ 行和 $i+1$ 行之间能隔开的交头接耳对数（上下相邻的对）。
   • 创建数组 col[1..N-1]：col[j] 表示第 $j$ 列和 $j+1$ 列之间能隔开的交头接耳对数（左右相邻的对）。

2. 选择最优通道：

   • 将 row 按值从大到小排序（值相同按位置从小到大），取前 $K$ 个位置。
   • 将 col 按值从大到小排序（值相同按位置从小到大），取前 $L$ 个位置。
   • 由于题目要求输出位置从小到大，需对选中的位置再排序。

3. 输出结果：

   • 第一行输出 $K$ 个横向通道位置（从小到大）。
   • 第二行输出 $L$ 个纵向通道位置（从小到大）。

---

代码实现（可食）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

//排序
struct Node {
    int pos;    //位置
    int cnt;    //隔开的人
};

//按人数从大到小排，人数相同按位置从小到大
bool cmp(Node a, Node b) {
    if (a.cnt != b.cnt) return a.cnt > b.cnt;
    return a.pos < b.pos;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);//哈德森（加速）

    int M, N, K, L, D;
    cin >> M >> N >> K >> L >> D;

    vector<int> row(M + 1, 0); //第i行和i+1行之间的通道价值
    vector<int> col(N + 1, 0); //第i列和i+1列之间的通道价值

    //统计
    for (int i = 0; i < D; ++i) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;

        if (x1 == x2) {
            int c = min(y1, y2);
            col[c]++;
        }
        else {
            int r = min(x1, x2);
            row[r]++;
        }
    }

    vector<Node> rows, cols;
    for (int i = 1; i <= M - 1; ++i) rows.push_back({ i, row[i] });
    for (int i = 1; i <= N - 1; ++i) cols.push_back({ i, col[i] });

    sort(rows.begin(), rows.end(), cmp);
    sort(cols.begin(), cols.end(), cmp);

    vector<int> ans_r, ans_c;
    for (int i = 0; i < K; ++i) ans_r.push_back(rows[i].pos);
    for (int i = 0; i < L; ++i) ans_c.push_back(cols[i].pos);

    sort(ans_r.begin(), ans_r.end());
    sort(ans_c.begin(), ans_c.end());

    for (int i = 0; i < ans_r.size(); ++i) {
        if (i > 0) cout << " ";
        cout << ans_r[i];
    }
    cout << endl;

    for (int i = 0; i < ans_c.size(); ++i) {
        if (i > 0) cout << " ";
        cout << ans_c[i];
    }
    cout << endl;

    return 0;//不忘
}

---

复杂度分析

• 时间复杂度：$O(D + (M + N) \log (M + N))$
  • $D$：统计交头接耳对。
  • $(M + N) \log (M + N)$：排序行/列价值。
• 空间复杂度：$O(M + N)$
  • 存储 row、col 和排序数组。

---

正确关键

• 贪心策略：选择能隔开最多交头接耳对的通道，最大化减少交头接耳对数。
• 唯一性保证：题目输入保证最优方案唯一，排序规则（价值大优先，位置小优先）确保输出唯一。
• 边界处理：row 和 col 索引从 1 开始，覆盖 $1$ 到 $M-1$ 和 $1$ 到 $N-1$。

本题本质是最大化被隔开的交头接耳对数，通过统计每行/列间的价值并贪心选择，即可得到最优解。