首页 > 试题广场 >

排座椅

[编程题]排座椅
  • 热度指数：85 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 50M，其他语言100M
  • 算法知识视频讲解
\hspace{15pt}教室内共有 n 行 m 列座位，坐在第 i 行第 j 列同学的位置记为 (i,j)。

\hspace{15pt}为了方便进出，班主任计划设置 k 条横向通道（贯穿整列的水平通道）与 l 条纵向通道（贯穿整行的竖直通道）。通道位于相邻两行（或两列）之间。

\hspace{15pt}班主任记录了 d 对经常交头接耳的同学，他们的位置 (x_i,y_i) 与 (p_i,q_i) 保证相邻（上下或左右）。她希望通过合理放置通道，使尽可能多的"交头接耳"对被通道隔开。

\hspace{15pt}现请你输出唯一的最优方案，在该方案下，仍未被通道隔开的"交头接耳"对的数量最少。

输入描述:
\hspace{15pt}第一行输入五个整数 n,m,k,l,d\left(2\leqq n,m\leqq 10^3;\ 0<k<n;\ 0<l<m;\ 0< d \leqq 2\times\min\{n\times m,2\times10^3\}\right)。

\hspace{15pt}接下来 d 行，每行输入四个整数 x_i,y_i,p_i,q_i，表示坐标 (x_i,y_i) 与 (p_i,q_i) 的两位同学会交头接耳，且两坐标上下相邻或左右相邻。

\hspace{15pt}保证最优方案存在且唯一。


输出描述:
\hspace{15pt}第一行输出 k 个严格递增的整数 a_1,a_2,\dots,a_k\left(1\leqq a_1<\dots<a_k\leqq n-1\right)，在行 a_i 与 a_i+1 之间设置横向通道。

\hspace{15pt}第二行输出 l 个严格递增的整数 b_1,b_2,\dots,b_l\left(1\leqq b_1<\dots<b_l\leqq m-1\right)，在列 b_i 与 b_i+1 之间设置纵向通道。
示例1

输入

4 5 1 2 3
4 2 4 3
2 3 3 3
2 5 2 4

输出

2
2 4

说明

\hspace{15pt}该样例如下图所示，蓝底斜线方格为第一对交头接耳的同学，绿底带叉方格为第二对交头接耳的同学，粉底带星方格为第三对交头接耳的同学。粗线代表通道。该划分方案为唯一最优方案。

示例2

输入

2 2 1 1 4
1 1 1 2
1 1 2 1
2 1 2 2
1 2 2 2

输出

1
1
算法知识视频讲解
添加回答
C++
NixihsiaL头像 NixihsiaL
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Interval {
    int pos;
    int count;
};

bool compare(const Interval& a, const Interval& b) {
    return a.count > b.count;
}

int main() {
    int n, m, k, l, d;
    cin >> n >> m >> k >> l >> d;

    vector<Interval> row_gaps(n - 1, {0, 0});
    vector<Interval> col_gaps(m - 1, {0, 0});

    for (int i = 0; i < d; ++i) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        //统计使用某条通道的次数
        if (x1 == x2) {
            int col = min(y1, y2) - 1;
            col_gaps[col].count++;
            col_gaps[col].pos = col + 1;
        } else {
            int row = min(x1, x2) - 1;
            row_gaps[row].count++;
            row_gaps[row ].pos = row + 1;
        }
    }

    sort(row_gaps.begin(), row_gaps.end(), compare);
    sort(col_gaps.begin(), col_gaps.end(), compare);

    vector<int> selected_rows, selected_cols;
    //将使用最频繁的通道取出
    for (int i = 0; i < k; ++i) {
        selected_rows.push_back(row_gaps[i].pos);
    }
    for (int i = 0; i < l; ++i) {
        selected_cols.push_back(col_gaps[i].pos);
    }
    //保证结果从小到大输出
    sort(selected_rows.begin(), selected_rows.end());
    sort(selected_cols.begin(), selected_cols.end());

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

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

    return 0;
}
发表于 2025-07-09 15:31:16 回复(0)
游客_1400000000头像 游客_1400000000
有人会吗
发表于 2025-06-23 14:35:20 回复(0)
提交观点

问题信息

难度：
2条回答 38浏览

热门推荐

相关试题

排座椅

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号