首页 > 试题广场 >

排座椅

[编程题]排座椅

热度指数：3290 时间限制：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}$ 现请你输出唯一的最优方案，在该方案下，仍未被通道隔开的"交头接耳"对的数量最少。

输入描述:

第一行输入五个整数 。

接下来  行，每行输入四个整数 ，表示坐标  与  的两位同学会交头接耳，且两坐标上下相邻或左右相邻。

保证最优方案存在且唯一。

输出描述:

第一行输出  个严格递增的整数 ，在行  与  之间设置横向通道。

第二行输出  个严格递增的整数 ，在列  与  之间设置纵向通道。

示例1

输入

输出

2
2 4

说明

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

示例2

输入

输出

1
1

算法知识视频讲解

conv_lstm

发表于 2025-08-05 22:38:36

#include <functional> #include <iostream> #include <unordered_map> #include<vector> #include<algorithm> using namespace 展开全文

周康禧

发表于 2025-12-21 12:03:59

对行列横竖分别考虑，因为不会相互影响，因为要最小化，所以考虑贪心，按每次设计走廊分隔的个数排序然后记录一下下标排序输出就可以了 struct R{ int x; int id; }; bool cmp(R a,R b){ return a.x>b.x; } void s 展开全文

BraveCoder

发表于 2025-09-03 21:18:43

import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc. 展开全文

BaiJay

发表于 2025-12-21 08:33:11

这道题本身就是一个**“建模 + 贪心统计”的经典题型一、题意重新梳理（把问题“翻译成人话”）教室是一个 n 行 m 列的网格同学坐在 (i, j)。可以修：k 条横向通道（在第 ai 行和 ai+1 行之间）l 条纵向通道（在第 bi 列和 bi+1 列之间）有 d 对“经常交头接耳”的同学展开全文

学习小生

发表于 2025-09-06 21:58:07

n, m, k, l, d = map(int, input().split()) row = {} col = {} for _ in range(d): x, y, p, q = map(int, input().split()) if x == p: min_c 展开全文

quchen666

发表于 2025-12-21 12:51:24

#include <bits/stdc++.h> using namespace std; const int N = 2e3+10; struct Node { int cnt=0; int id; }; Node a[N]; Node b[N]; bool cm 展开全文

Jakeap

发表于 2025-12-21 17:49:29

突破点1：仔细审题能发现交谈对总是相互挨着，那么一定是横坐标相等纵坐标差一或者纵坐标相等横坐标差一，又发现分割线横线和竖线的数量是给定的，那么这两种线互不干扰，那么从二维转换为一维问题。就用两个数组分别存交谈对数。突破点2：收集横坐标i和i+1之间有交谈对的数量，纵坐标也是如此，那么最后分别对两个数展开全文

zhenghahahawda

发表于 2025-08-03 18:21:39

#include <algorithm> #include <unordered_map> #include <iostream> #include <vector> using namespace std; bool cmp(const pair& 展开全文

手有余湘

发表于 2025-08-04 11:06:29

n,m,k,l,d=list(map(int,input().split())) hengxiang={} shuxiang={} for i in range(d): ceshi=list(map(int,input().split())) if ceshi[0]==ceshi[2 展开全文

香泥乐铁汁

发表于 2025-08-28 11:23:16

import java.util.*; import java.util.stream.Collectors; // 注意类名必须为 Main, 不要有任何 package xxx 信息 /* 思路：先找出横向、纵向的“交头接耳”对的数量再找出前k个横展开全文

问题信息

贪心

难度：

15条回答 34收藏 329浏览

排座椅

输入描述:

输出描述:

输入

输出

说明

输入

输出

问题信息

热门推荐

相关试题