题解 P1056 【排座椅】

### 这种题目其实比较简单，感谢楼下给我的灵感~ ## 由于题目是要求最多能隔开多少对会交头接耳的同学，我们可以用贪心轻松求解（幸好走廊的行数列数都是固定的），只需要**得到隔开交头接耳的同学最多的 k 条横向的通道和 l 条纵向的通道**就可以了！掌声响起来~ ## 过程大概是这个样子： ### 1. 定义两个数组 a 和 b，分别储存行和列的通道可隔开的交头接耳的同学的对数； ### 2. 将 a 和 b 按可所隔开的同学的对数从大到小排序 ### 3. 输出 a 的前 k 个元素所代表的通道的位置和 b 的前 l 个元素所代表的通道的位置。 代码如下： ```cpp #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; } ```