排座椅

思路

这道题乍一看挺唬人的——教室里 m 行 n 列座位，要放 h 条横向通道和 v 条纵向通道，让尽可能多的"交头接耳对"被隔开。怎么放才最优？

先别急，想想看：一对交头接耳的同学，要么是上下相邻，要么是左右相邻。如果他们上下相邻，只有在他们之间那一行放横向通道才能隔开；如果左右相邻，只有在他们之间那一列放纵向通道才能隔开。也就是说，横向通道和纵向通道是互相独立的，可以分开处理。

怎么贪心？

既然横向和纵向独立，那问题就变成了：

  • 统计每条"行间隙"（第 i 行和第 i+1 行之间）能隔开多少对上下相邻的同学
  • 统计每条"列间隙"（第 j 列和第 j+1 列之间）能隔开多少对左右相邻的同学

然后贪心地选隔开最多的 h 个行间隙和 v 个列间隙就行了。最后按递增顺序输出。

为什么贪心是对的？因为每对同学只可能被恰好一条通道隔开，选哪条通道不会影响其他通道的收益，不存在冲突，所以直接挑收益最大的就是全局最优。

实现步骤

  1. 读入 k 对同学坐标，判断是上下相邻还是左右相邻
  2. 上下相邻 → row[min(r1,r2)]++；左右相邻 → col[min(c1,c2)]++
  3. 对行间隙按计数排序，取前 h 个；对列间隙按计数排序，取前 v 个
  4. 把选出的间隙编号排序后输出

代码

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

int main() {
    int m, n, h, v, k;
    cin >> m >> n >> h >> v >> k;

    vector<int> row(m + 1, 0);
    vector<int> col(n + 1, 0);

    for (int i = 0; i < k; i++) {
        int r1, c1, r2, c2;
        cin >> r1 >> c1 >> r2 >> c2;
        if (r1 == r2) {
            col[min(c1, c2)]++;
        } else {
            row[min(r1, r2)]++;
        }
    }

    // 按隔开对数排序，选前 h / v 个
    vector<pair<int,int>> rows, cols;
    for (int i = 1; i < m; i++) rows.push_back({-row[i], i});
    for (int j = 1; j < n; j++) cols.push_back({-col[j], j});

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

    vector<int> hres, vres;
    for (int i = 0; i < h; i++) hres.push_back(rows[i].second);
    for (int i = 0; i < v; i++) vres.push_back(cols[i].second);

    sort(hres.begin(), hres.end());
    sort(vres.begin(), vres.end());

    for (int i = 0; i < h; i++) {
        if (i) cout << " ";
        cout << hres[i];
    }
    cout << endl;
    for (int i = 0; i < v; i++) {
        if (i) cout << " ";
        cout << vres[i];
    }
    cout << endl;

    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt(), n = sc.nextInt(), h = sc.nextInt(), v = sc.nextInt(), k = sc.nextInt();

        int[] row = new int[m + 1];
        int[] col = new int[n + 1];

        for (int i = 0; i < k; i++) {
            int r1 = sc.nextInt(), c1 = sc.nextInt(), r2 = sc.nextInt(), c2 = sc.nextInt();
            if (r1 == r2) {
                col[Math.min(c1, c2)]++;
            } else {
                row[Math.min(r1, r2)]++;
            }
        }

        int[][] rows = new int[m - 1][2];
        for (int i = 1; i < m; i++) { rows[i-1][0] = -row[i]; rows[i-1][1] = i; }
        int[][] cols = new int[n - 1][2];
        for (int j = 1; j < n; j++) { cols[j-1][0] = -col[j]; cols[j-1][1] = j; }

        Arrays.sort(rows, (a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
        Arrays.sort(cols, (a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);

        int[] hres = new int[h], vres = new int[v];
        for (int i = 0; i < h; i++) hres[i] = rows[i][1];
        for (int i = 0; i < v; i++) vres[i] = cols[i][1];

        Arrays.sort(hres);
        Arrays.sort(vres);

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < h; i++) { if (i > 0) sb.append(" "); sb.append(hres[i]); }
        System.out.println(sb.toString());
        sb = new StringBuilder();
        for (int i = 0; i < v; i++) { if (i > 0) sb.append(" "); sb.append(vres[i]); }
        System.out.println(sb.toString());
    }
}

import sys
input = sys.stdin.readline

m, n, h, v, k = map(int, input().split())
row = [0] * (m + 1)
col = [0] * (n + 1)
for _ in range(k):
    r1, c1, r2, c2 = map(int, input().split())
    if r1 == r2:
        col[min(c1, c2)] += 1
    else:
        row[min(r1, r2)] += 1

rows = [(-row[i], i) for i in range(1, m)]
cols = [(-col[j], j) for j in range(1, n)]
rows.sort()
cols.sort()

hres = sorted([rows[i][1] for i in range(h)])
vres = sorted([cols[i][1] for i in range(v)])

print(' '.join(map(str, hres)))
print(' '.join(map(str, vres)))

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
    const [m, n, h, v, k] = lines[0].split(' ').map(Number);
    const row = new Array(m + 1).fill(0);
    const col = new Array(n + 1).fill(0);
    for (let i = 1; i <= k; i++) {
        const [r1, c1, r2, c2] = lines[i].split(' ').map(Number);
        if (r1 === r2) {
            col[Math.min(c1, c2)]++;
        } else {
            row[Math.min(r1, r2)]++;
        }
    }
    const rows = [];
    for (let i = 1; i < m; i++) rows.push([-row[i], i]);
    const cols = [];
    for (let j = 1; j < n; j++) cols.push([-col[j], j]);
    rows.sort((a, b) => a[0] !== b[0] ? a[0] - b[0] : a[1] - b[1]);
    cols.sort((a, b) => a[0] !== b[0] ? a[0] - b[0] : a[1] - b[1]);
    const hres = [];
    for (let i = 0; i < h; i++) hres.push(rows[i][1]);
    const vres = [];
    for (let i = 0; i < v; i++) vres.push(cols[i][1]);
    hres.sort((a, b) => a - b);
    vres.sort((a, b) => a - b);
    console.log(hres.join(' '));
    console.log(vres.join(' '));
});

复杂度分析

  • 时间复杂度: ，统计 k 对同学后对行和列间隙排序
  • 空间复杂度: ，存储行列计数数组

总结

这题的关键洞察就一个：横向通道和纵向通道互不影响，可以分开贪心。想明白这一点，剩下的就是统计每个间隙能隔开几对同学，然后按收益排序、取前几个。贪心之所以成立，是因为每对同学只和一条可能的通道相关，选不选这条通道不影响其他通道的价值，没有决策冲突。