题解 | #排座椅#

题目链接

排座椅

题目描述

在一个 $r \times c$ 的教室里，有 $k$ 对相邻的同学会交头接耳。班主任计划设置 $h$ 条横向通道和 $v$ 条纵向通道，来隔开这些同学。

横向通道设置在相邻两行之间。
纵向通道设置在相邻两列之间。

目标是找到一个最优的通道设置方案，使得被通道隔开的“交头接耳”对数量最多。题目保证最优方案唯一。请输出这个方案。

解题思路

这是一个典型的贪心问题。关键的洞察在于，横向通道的放置决策与纵向通道的放置决策是相互独立的。

一条横向通道只能隔开上下相邻的同学。
一条纵向通道只能隔开左右相邻的同学。

因此，我们可以将原问题分解为两个独立的子问题：

找到最优的 $h$ 个位置来放置横向通道。
找到最优的 $v$ 个位置来放置纵向通道。

贪心策略 对于每个子问题，我们的目标是让放置的每一条通道都能发挥最大的作用，即隔开尽可能多的交头接耳对。

对于横向通道：
1. 首先，我们需要统计出在每一行之间（即 (i, i+1) 行之间）有多少对上下相邻的同学在交头接耳。我们可以用一个数组 h_counts 来记录，h_counts[i] 表示在第 $i$ 行和第 $i+1$ 行之间设置通道能隔开的对数。
2. 统计完成后，h_counts 中数值最大的 $h$ 个位置，就是我们应该放置横向通道的地方，因为它们能隔开最多的对数。
对于纵向通道：
1. 同理，我们统计出在每一列之间（即 (j, j+1) 列之间）有多少对左右相邻的同学在交头接耳。用数组 v_counts 记录。
2. 选择 v_counts 中数值最大的 $v$ 个位置来放置纵向通道。

算法步骤

初始化：创建两个计数数组，h_counts（大小为 $r$ ）和 v_counts（大小为 $c$ ），均初始化为0。
统计：遍历 $k$ 对交头接耳的同学：
- 对于一对同学 $(r_1, c_1)$ 和 $(r_2, c_2)$ ：
  - 如果他们是上下相邻（ $c_1 = c_2$ ），则在第 $\min(r_1, r_2)$ 行下方的通道能隔开他们。于是 h_counts[min(r1, r2)]++。
  - 如果他们是左右相邻（ $r_1 = r_2$ ），则在第 $\min(c_1, c_2)$ 列右方的通道能隔开他们。于是 v_counts[min(c1, c2)]++。
选择横向通道：
- 将 h_counts 数组中的计数和对应的行号（从1到 $r-1$ ）配对，例如存入 (count, row_index) 这样的结构中。
- 根据 count 对这些配对进行降序排序。
- 选取排序后的前 $h$ 个配对，它们的 row_index 就是最优的横向通道位置。
选择纵向通道：
- 对 v_counts 执行与上一步类似的操作，选出前 $v$ 个最优的纵向通道位置。
输出结果：
- 将选出的 $h$ 个横向通道位置升序排序后输出。
- 将选出的 $v$ 个纵向通道位置升序排序后输出。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 用于排序的结构体
struct Candidate {
    int count;
    int index;
};

bool compareCandidates(const Candidate& a, const Candidate& b) {
    return a.count > b.count;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int r, c, h, v, k;
    cin >> r >> c >> h >> v >> k;

    vector<int> h_counts(r + 1, 0);
    vector<int> v_counts(c + 1, 0);

    for (int i = 0; i < k; ++i) {
        int r1, c1, r2, c2;
        cin >> r1 >> c1 >> r2 >> c2;
        if (r1 == r2) { // 左右相邻
            v_counts[min(c1, c2)]++;
        } else { // 上下相邻
            h_counts[min(r1, r2)]++;
        }
    }

    vector<Candidate> h_candidates;
    for (int i = 1; i < r; ++i) {
        h_candidates.push_back({h_counts[i], i});
    }
    sort(h_candidates.begin(), h_candidates.end(), compareCandidates);

    vector<int> h_results;
    for (int i = 0; i < h; ++i) {
        h_results.push_back(h_candidates[i].index);
    }
    sort(h_results.begin(), h_results.end());

    vector<Candidate> v_candidates;
    for (int i = 1; i < c; ++i) {
        v_candidates.push_back({v_counts[i], i});
    }
    sort(v_candidates.begin(), v_candidates.end(), compareCandidates);

    vector<int> v_results;
    for (int i = 0; i < v; ++i) {
        v_results.push_back(v_candidates[i].index);
    }
    sort(v_results.begin(), v_results.end());

    for (int i = 0; i < h; ++i) {
        cout << h_results[i] << (i == h - 1 ? "" : " ");
    }
    cout << endl;

    for (int i = 0; i < v; ++i) {
        cout << v_results[i] << (i == v - 1 ? "" : " ");
    }
    cout << endl;

    return 0;
}

import java.util.*;

class Candidate {
    int count;
    int index;

    public Candidate(int count, int index) {
        this.count = count;
        this.index = index;
    }
}

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

        int[] hCounts = new int[r + 1];
        int[] vCounts = new int[c + 1];

        for (int i = 0; i < k; i++) {
            int r1 = sc.nextInt();
            int c1 = sc.nextInt();
            int r2 = sc.nextInt();
            int c2 = sc.nextInt();
            if (r1 == r2) { // 左右相邻
                vCounts[Math.min(c1, c2)]++;
            } else { // 上下相邻
                hCounts[Math.min(r1, r2)]++;
            }
        }

        List<Candidate> hCandidates = new ArrayList<>();
        for (int i = 1; i < r; i++) {
            hCandidates.add(new Candidate(hCounts[i], i));
        }
        hCandidates.sort((a, b) -> b.count - a.count);

        List<Integer> hResults = new ArrayList<>();
        for (int i = 0; i < h; i++) {
            hResults.add(hCandidates.get(i).index);
        }
        Collections.sort(hResults);

        List<Candidate> vCandidates = new ArrayList<>();
        for (int i = 1; i < c; i++) {
            vCandidates.add(new Candidate(vCounts[i], i));
        }
        vCandidates.sort((a, b) -> b.count - a.count);

        List<Integer> vResults = new ArrayList<>();
        for (int i = 0; i < v; i++) {
            vResults.add(vCandidates.get(i).index);
        }
        Collections.sort(vResults);
        
        for (int i = 0; i < h; i++) {
            System.out.print(hResults.get(i) + (i == h - 1 ? "" : " "));
        }
        System.out.println();

        for (int i = 0; i < v; i++) {
            System.out.print(vResults.get(i) + (i == v - 1 ? "" : " "));
        }
        System.out.println();
    }
}

import sys

def solve():
    r, c, h, v, k = map(int, sys.stdin.readline().split())
    
    h_counts = [0] * (r + 1)
    v_counts = [0] * (c + 1)
    
    for _ in range(k):
        r1, c1, r2, c2 = map(int, sys.stdin.readline().split())
        if r1 == r2: # 左右相邻
            v_counts[min(c1, c2)] += 1
        else: # 上下相邻
            h_counts[min(r1, r2)] += 1
            
    # --- 处理横向通道 ---
    h_candidates = []
    for i in range(1, r):
        h_candidates.append((h_counts[i], i))
    
    # 按count降序排序
    h_candidates.sort(key=lambda x: x[0], reverse=True)
    
    h_results = []
    for i in range(h):
        h_results.append(h_candidates[i][1])
    
    h_results.sort() # 按index升序排序
    
    # --- 处理纵向通道 ---
    v_candidates = []
    for i in range(1, c):
        v_candidates.append((v_counts[i], i))
        
    v_candidates.sort(key=lambda x: x[0], reverse=True)
    
    v_results = []
    for i in range(v):
        v_results.append(v_candidates[i][1])
        
    v_results.sort()
    
    print(*h_results)
    print(*v_results)

solve()

算法及复杂度

算法：贪心
时间复杂度：
- 统计所有交头接耳对的位置需要 $\mathcal{O}(k)$ 。
- 对横向通道候选位置进行排序需要 $\mathcal{O}(r \log r)$ 。
- 对纵向通道候选位置进行排序需要 $\mathcal{O}(c \log c)$ 。
- 总时间复杂度为 $\mathcal{O}(k + r \log r + c \log c)$ 。
空间复杂度：需要两个数组来存储每个通道位置的计数，空间复杂度为 $\mathcal{O}(r+c)$ 。