排座椅
排座椅
https://ac.nowcoder.com/acm/problem/16618
题意
班里有m行n列个座位，一共有d对同学紧挨着（前后或者左右）喜欢讲话，小雪可以在教室中设置了K条横向的通道，L条纵向的通道，通道可以分开挨着的同学，问通道设置在什么位置可以使班上讲话的人数最少。
题解
简单的贪心。每条通道肯定是能分开的同学越多越好，所以枚举喜欢讲话的同学，将他们之间的路记录下来，行和列用不同的数组记录，然后行和列都由大到小排序路的个数。排序后，将行中前K个路按照路的编号由小到大排序后输出这K条路，列中前L个路也同样操作。
代码
#include<bits/stdc++.h>
using namespace std;
struct node
{
int res,id;
}a[100100],b[100100];
int cmp(node x,node y)
{
return x.res>y.res;
}
int cmp2(node x,node y)
{
return x.id<y.id;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n,m,k,l,d;
cin>>n>>m>>k>>l>>d;
int k1=0,k2=0;
for(int i=0;i<d;i++){
int x1,x2,y1,y2;
cin>>x1>>y1>>x2>>y2;
if(x1==x2){
int y=min(y1,y2);
b[y].id=y;
b[y].res++;
}
else {
int x=min(x1,x2);
a[x].id=x;
a[x].res++;
}
}
sort(a+1,a+1+m,cmp);
sort(b+1,b+1+n,cmp);
sort(a+1,a+1+k,cmp2);
sort(b+1,b+1+l,cmp2);
for(int i=1;i<=k;i++) {
if(!a[i].id) break;
cout<<a[i].id<<' ';
}
cout<<endl;
for(int i=1;i<=l;i++) {
if(!b[i].id) break;
cout<<b[i].id<<' ';
}
cout<<endl;
return 0;
}
vivo公司福利 698人发布