首页 > 试题广场 >

排座椅

[编程题]排座椅

热度指数：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

算法知识视频讲解

Python3

牛客341639822号

from collections import Counter
row, col, r, c, d = map(int, input().split())
r_list = []
c_list = [] for i in range(d):
    ds = [int(x) for x in input().split()] if ds[0] == ds[2]:
        value = min(ds[1], ds[3])
        c_list.append(value) else:
        value = min(ds[0], ds[2])
        r_list.append(value)
count_r = sorted(Counter(r_list).items(), key=lambda items: items[1],reverse=True)
count_c = sorted(Counter(c_list).items(), key=lambda items: items[1],reverse=True) if len(set(r_list)) > r:
    result_r = [] for i in range(r):
        result_r.append(count_r[i][0])
    result_r = map(str, sorted(result_r)) print(' '.join(result_r)) else:
    result_r = map(str, sorted(set(r_list))) print(' '.join(result_r)) if len(set(c_list)) > c:
    result_c = [] for i in range(c):
        result_c.append(count_c[i][0])
    result_c = map(str, sorted(result_c)) print(' '.join(result_c)) else:
    result_c = map(str, sorted(set(c_list))) print(' '.join(result_c))

发表于 2025-10-04 10:47:33 回复(0)

Python3

忧伤的双曲线

n,m,k,l,d = map(int,input().split())

dic_heng = {}

dic_zong = {}

for i in range(d):

x,y,p,q = map(int,input().split())

if x==p:

if min(y,q) not in dic_zong.keys():

dic_zong[min(y,q)] = 1

else:

dic_zong[min(y,q)] += 1

elif y==q:

if min(x,p) not in dic_heng.keys():

dic_heng[min(x,p)] = 1

else:

dic_heng[min(x,p)] += 1

list_heng = sorted(dic_heng,key=lambda x:-dic_heng[x])

list_zong = sorted(dic_zong,key=lambda x:-dic_zong[x])

print(' '.join(map(str,sorted(list_heng[0:k]))))

print(' '.join(map(str,sorted(list_zong[0:l]))))

发表于 2025-09-25 00:35:34 回复(0)

提交观点

问题信息

贪心

难度：

2条回答 34收藏 328浏览

排座椅

输入描述:

输出描述:

输入

输出

说明

输入

输出

问题信息

热门推荐

相关试题