题解 P1056 【排座椅】

题目地址：https://www.luogu.com.cn/problem/P1056

题解原地址：https://createsj.blog.luogu.org/solution-p1056

由于题目是要求最多能隔开多少对会交头接耳的同学，我们可以用贪心轻松求解（幸好走廊的行数列数都是固定的），只需要得到隔开交头接耳的同学最多的 k 条横向的通道和 l 条纵向的通道就可以了！掌声响起来~

过程大概是这个样子：

定义两个数组 a 和 b，分别储存行和列的通道可隔开的交头接耳的同学的对数；
将 a 和 b 按可所隔开的同学的对数从大到小排序
输出 a 的前 k 个元素所代表的通道的位置和 b 的前 l 个元素所代表的通道的位置。

代码如下：

#include <cstdio>

#include <cstring>

#include <algorithm>

#define MIN(A,B) ((A<B)?A:B)//求两个数中的最小值

using namespace std;

struct st//定义一个结构体,储存在第 l 行/列和第 r 行/列之间插入走廊后能隔开 v 对同学

{

	int v,l,r;

}*a/*行*/,*b/*列*/;

inline bool cmp1(const st x,const st y)

{

	return x.v>y.v;

}

inline bool cmp2(const st x,const st y)

{

	return x.l<y.l;

}

int main()

{

	int m,n,k,l,d;

	scanf("%d %d %d %d %d",&m,&n,&k,&l,&d);

	//为 a,b 动态分配内存,也可之间用 a[1001],b[1001],不过本人只是想省省内存

	a=new st[m+1];

	b=new st[n+1];

	//初始化

	memset(a,0,sizeof(st)*n);//数组 a 清零

	memset(b,0,sizeof(st)*n);//数组 b 清零

	//初始化 l 和 r

	for(int i=1;i<m;i++)

		a[i].l=i,a[i].r=i+1;

	for(int i=1;i<n;i++)

		b[i].l=i,b[i].r=i+1;

	//输入和处理输入数据

	for(int i=0,x,y,p,q;i<d;i++)

	{

		scanf("%d %d %d %d",&x,&y,&p,&q);

		if(x!=p)//如果 x!=p,说明两名同学不在同一行,所以就在同一列

			a[MIN(x,p)].v++;

		else//否则,说明两名同学在同一行

			b[MIN(y,q)].v++;

	}

	sort(a,a+m,cmp1);//以 v 来为数组 a 从小到大排序

	sort(a,a+k,cmp2);//以插入顺序来为数组 a 的前 k 个元素排序

	sort(b,b+n,cmp1);//以 v 来为数组 b 从小到大排序

	sort(b,b+l,cmp2);//以插入顺序来为数组 b 的前 l 个元素排序

	//输出

	for(int i=0;i<k;i++)

		printf("%d ",a[i].l);

	putchar('\n');

	for(int i=0;i<l;i++)

		printf("%d ",b[i].l);

	//清空动态分配的内存

	delete [] a;

	delete [] b;

	return 0;

}

巴特西

题解 P1056 【排座椅】

最新文章

热门文章