洛谷 P1056 排座椅 桶排序

时间:2023-03-08 16:52:36
洛谷 P1056 排座椅 桶排序

桶排序大法好!

每次一看到这种范围小的题,本萌新就想用桶排。

因为题目中的m,n都小于1000,我们就可以定义两个1000的数组,表示每一行或每一列可以隔开几对讲话的童鞋。

然后再定义两个1000的数组用来对前两个数组的值进行桶排序,再用通道总数从大到小减下去直到为零,记录最后这个数,凡是能隔开这么多对讲话的同学的通道,就能输出。

主要程序:

#include<iostream>
using namespace std;
int a[1001],b[1001],p[1001],q[1001];
int c1,c2,c3,c4,i,j,o,m,n,k,l,d;//准备工作
int main(){
cin>>m>>n>>k>>l>>d;//输入
for(i=1;i<=d;i++){
cin>>c1>>c2>>c3>>c4;
if(c1==c3)b[min(c2,c4)]++;//行相同,两个同学中间那一列加一
else a[min(c1,c3)]++;//列相同,行增加
}
for(i=1000;i>=1;i--){
if(a[i])p[a[i]]++;//对行能隔开的同学数桶排序
if(b[i])q[b[i]]++;//对列能隔开的同学数桶排序
}
for(i=1000;k>0;i--)if(p[i])k-=p[i];//*用总行(列)数从大往小减,得出来的数为
for(j=1000;l>0;j--)if(q[j])l-=q[j];//要输出的行列最小应该达到的隔开同学的数目
for(o=1;o<=1000;o++)if(a[o]>i)cout<<o<<" ";
cout<<endl;//换行符别丢了
for(o=1;o<=1000;o++)if(b[o]>j)cout<<o<<" ";
return 0;
}

这是我的博客,发的题解和一些洛谷技巧都在里面。

另外,本人真的只是一个弱弱的萌新,7月份才入信息组,发的题解讨论等级不高,新人可看。