题解 | #排座椅#

本题的核心目标是在有限的资源约束下（ 条横向通道， 条纵向通道），最大化被物理隔离的交头接耳学生对数。

1. 问题分析 首先需要识别出一个关键的的几何特性：横向通道与纵向通道的作用范围是相互正交且独立的。

• 横向通道（Horizontal Channel）：设置在行 和行 之间。它只能隔开位于同一列、但在相邻行（上下相邻）的学生对。它无法隔开左右相邻的学生。
• 纵向通道（Vertical Channel）：设置在列 和列 之间。它只能隔开位于同一行、但在相邻列（左右相邻）的学生对。它无法隔开上下相邻的学生。

基于这种正交性，我们可以将原本的二维优化问题拆解为两个独立的一维优化问题：

1. 行分割子问题：在 个可能的行间隙中选择 个，以隔开最多的上下相邻对。
2. 列分割子问题：在 个可能的列间隙中选择 个，以隔开最多的左右相邻对。

2. 数据规模

• 规模：，交头接耳对数 。这意味着即使是 或 的算法也是完全可以接受的，无需过度优化。
• 唯一性保证：题目保证最优方案唯一，这消除了排序时处理并列情况（Tie-breaking）的复杂性。
• 输出要求：输出的通道位置必须严格递增。这暗示我们在通过贪心策略选出最佳位置后，必须对这些选定的位置索引进行二次排序。

贪心算法

由于每个通道的选择对总目标的贡献是累加的，且不存在一种情况使得“当前选择较差的通道位置是为了将来能选更好的（因为位置之间没有依赖关系）”，因此贪心策略是本题的最优解且可以证明其正确性。

核心逻辑：

1. 统计贡献度：遍历所有的 对学生。
   • 如果是上下相邻（行坐标不同，列坐标相同），则这两个行之间的间隙的“潜在贡献值”加 1。
   • 如果是左右相邻（行坐标相同，列坐标不同），则这两个列之间的间隙的“潜在贡献值”加 1。
2. 按贡献排序：将所有行间隙按“潜在贡献值”从大到小排序；将所有列间隙按“潜在贡献值”从大到小排序。
3. 最优截取：
   • 取排序后前 个行间隙。
   • 取排序后前 个列间隙。
4. 索引重排：由于题目要求输出的通道编号必须是从小到大排列的（例如输出 2 4 而不是 4 2），我们需要对上一步选出的 个行索引和 个列索引分别进行升序排序。

复杂度分析

假设行数为 ，列数为 ，学生对数为 。

1. 时间复杂度

• 统计过程：遍历 对学生，常数时间计算，耗时 。
• 排序过程（按贡献值）：
  • 对行间隙排序：涉及 个元素，耗时 。
  • 对列间隙排序：涉及 个元素，耗时 。
• 排序过程（按索引）：
  • 对选出的 个行索引排序：。
  • 对选出的 个列索引排序：。
• 总时间复杂度：。
  • 带入最大值计算： 约等于 次运算，远低于一般竞赛题目的 次/秒的限制。

2. 空间复杂度

• 需要两个数组（或哈希表）存储每个行间隙和列间隙的计数值。
• 空间复杂度为 。

代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Constraint {
    int index;
    int count;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, k, l, d;
    cin >> n >> m >> k >> l >> d;

    vector<Constraint> RowConstraint;
    vector<Constraint> ColConstraint;

    for (int i = 1; i < n; i++) RowConstraint.push_back({i, 0});
    for (int j = 1; j < m; j++) ColConstraint.push_back({j, 0});

    for (int i = 0; i < d; i++) {
        int x, y, p, q;
        cin >> x >> y >> p >> q;

        if (x == p) {
            int idx = min(y, q);
            ColConstraint[idx - 1].count++;
        }
        if (y == q) {
            int idx = min(x, p);
            RowConstraint[idx - 1].count++;
        }
    }

    sort(RowConstraint.begin(), RowConstraint.end(), [](const auto & a,
    const auto & b) {
        return a.count > b.count;
    });

    sort(ColConstraint.begin(), ColConstraint.end(), [](const auto & a,
    const auto & b) {
        return a.count > b.count;
    });

    vector<int> resRow, resCol;
    for (int i = 0; i < k; i++) resRow.push_back(RowConstraint[i].index);
    for (int i = 0; i < l; i++) resCol.push_back(ColConstraint[i].index);

    sort(resRow.begin(), resRow.end());
    sort(resCol.begin(), resCol.end());

    for (int i = 0; i < k; i++) {
        cout << resRow[i] << (i == k - 1 ? "" : " ");
    }
    cout << "\n";

    for (int i = 0; i < l; i++) {
        cout << resCol[i] << (i == l - 1 ? "" : " ");
    }
    cout << "\n";
}