P1056-排座椅
题目描述
上课的时候总会有一些同学和前后左右的人交头接耳,这是令小学班主任十分头疼的一件事情。不过,班主任小雪发现了一些有趣的现象,当同学们的座次确定下来之后,只有有限的D对同学上课时会交头接耳。
同学们在教室中坐成了M行N列,坐在第i行第j列的同学的位置是(i,j),为了方便同学们进出,在教室中设置了K条横向的通道,L条纵向的通道。
于是,聪明的小雪想到了一个办法,或许可以减少上课时学生交头接耳的问题:她打算重新摆放桌椅,改变同学们桌椅间通道的位置,因为如果一条通道隔开了2个会交头接耳的同学,那么他们就不会交头接耳了。
请你帮忙给小雪编写一个程序,给出最好的通道划分方案。在该方案下,上课时交头接耳的学生的对数最少。
输入格式
第一行,有5个用空格隔开的整数,分别是M,N,K,L,D(2<=N,M<=1000,0<=k<M,0<=L<N,D<=2000) 接下来的D行,每行有4个用空格隔开的整数。第i行的4个整数X,Y,P,Q,表示坐在位置(X,Y)与(P,Q)的两个同学会交头接耳(输入保证他们前后相邻或者左右相邻)。
输入数据保证最优方案的唯一性。
输出格式
共两行。 第一行包含K个整数a1,a2,...ak,表示第a1行和a1+1行之间、第a2行和a2+1行之间、...、第ak行和第ak+1之间要开辟通道,其中ai<ai+1,每两个整数之间用空格隔开(行尾没有空格)。
输入输出样例
输入 #1 4 5 1 2 3 4 2 4 3 2 3 3 3 2 5 2 4 输出 #1 2 2 4
说明/提示
上图中用符号*、※、+标出了3对会交头接耳的学生的位置,图中3条粗线的位置表示通道,图示的通道划分方案是唯一的最佳方案。
思路
这道题其实可以用贪心的做法,因为前后桌谈话和左右桌谈话互不影响,前后桌只能用行隔开,左右桌只能用列隔开,所以只要把有尽量多的交头接耳学生对的行和列隔开就是最优解。 大致解法:可以先算出每一行及每一列上交头接耳的学生对数,分别存入kRow[1005]和lRow[1005]中,这时下标就分别是代表这一行或列有多少对交头接耳的学生,然后对这两个数组分别进行降序排序(注意因为下标与人数是对应关系,所以不能用sort),因为规定设置K条横向和L条纵向,所以各取前K个、L个元素,把这些元素的下标存入ks、ls数组,再对这两个数组进行升序排序,这里C++可以用sort函数,最后输出结果即可。
源码
#include<iostream>
#include<algorithm>
using namespace std;
int kRow[1005];
int lRow[1005];
int main(){
int row,col,k,l,d; //行,列,横向,纵向,说话对数
int x1,y1,x2,y2;
int ks[1005],ls[1005],maxk,maxl;
cin >> row >> col >> k >> l >> d;
for(int i = 0;i < d;i++) {
cin >> x1 >> y1 >> x2 >> y2;
if(x1==x2){
lRow[min(y1,y2)]++;
}
else if(y1==y2){
kRow[min(x1,x2)]++;
}
}
for(int i = 0;i < k;i++){
maxk = 1;
for(int j = 1;j <= row;j++){
if(kRow[j]>kRow[maxk])maxk = j;
}
ks[i] = maxk;
kRow[maxk] = 0;
}
for(int i = 0;i < l;i++){ //这两个排序基本一致,可以做成函数
maxl = 1;
for(int j = 1;j <= col;j++){
if(lRow[j]>lRow[maxl])maxl = j;
}
ls[i] = maxl;
lRow[maxl] = 0;
}
sort(ks,ks+k);
sort(ls,ls+l);
for(int i = 0;i < k-1;i++)cout << ks[i] << " ";
cout << ks[k-1] << endl;
for(int i = 0;i < l-1;i++)cout << ls[i] << " ";
cout << ls[l-1] << endl;
return 0;
}
相关文章
- 提升Transformer在不平稳时间序列预测上效果的方法
- 让一个模型兼容多种数据的3种方法
- 用检索的思路做时间序列预测是一种怎样的体验
- 盘点5类推荐系统中图学习解决冷启动问题的方法
- NLP技术在搜索推荐场景中的应用
- CTR预估中实现高效笛卡尔积特征交叉的方法
- 让时间序列预测结果更真实的损失函数
- Graph对比学习——新一代的图无监督预训练方法
- 分解学习+对比学习实现更清晰的时间序列预测建模
- 从NIPS'22的3篇文章看Vision Transformer最新研究进展
- 多模态预训练常见问题:为什么不同模态表征存在gap?
- 使用Domain Adaption提升小场景时间序列预测效果的方法
- EMNLP'22 语言模型训练方法优化工作
- 抽象之美—万物皆可设计
- ShardingJdbc分库分表浅谈
- 低代码开发浅析
- 1024的程序员是蒙娜丽莎
- Java这些最基础的知识,你还记得多少?
- 快速排序递归详解
- Spring架构浅析