题目描述

上课的时候总有一些同学和前后左右的人交头接耳，这是令小学班主任十分头疼的一件事情。不过，班主任小雪发现了一些有趣的现象，当同学们的座次确定下来之后，只有有限的D对同学上课时会交头接耳。同学们在教室中坐成了M行N列，坐在第i行第j列的同学的位置是（i，j），为了方便同学们进出，在教室中设置了K条横向的通道，L条纵向的通道。于是，聪明的小雪想到了一个办法，或许可以减少上课时学生交头接耳的问题：她打算重新摆放桌椅，改变同学们桌椅间通道的位置，因为如果一条通道隔开了两个会交头接耳的同学，那么他们就不会交头接耳了。
请你帮忙给小雪编写一个程序，给出最好的通道划分方案。在该方案下，上课时交头接耳的学生对数最少。

输入描述:

第一行，有5各用空格隔开的整数，分别是。
接下来D行，每行有4个用空格隔开的整数，第i行的4个整数，表示坐在位置与的两个同学会交头接耳（输入保证他们前后相邻或者左右相邻）。
输入数据保证最优方案的唯一性。

输出描述:

第一行包含K个整数，，表示第行和行之间、第行和第行之间、…、第行和第行之间要开辟通道，其中，每两个整数之间用空格隔开（行尾没有空格）。
第二行包含L个整数，，表示第列和列之间、第列和第列之间、…、第列和第列之间要开辟通道，其中，每两个整数之间用空格隔开（行尾没有空格）。

示例1

输入
4 5 1 2 3
4 2 4 3
2 3 3 3
2 5 2 4
输出
2
2 4

说明

上图中用符号*、※、+ 标出了3对会交头接耳的学生的位置，图中3条粗线的位置表示通道，图示的通道划分方案是唯一的最佳方案。

解答

题目大意:给你一个的矩阵和矩阵中若干相邻点的坐标,要求用尽量少且数量不超过K的横向线段和尽量少且数量不超过L的纵向线段来分隔开尽量多的相邻的点；

算法:贪心。

每次读入两个相邻点时判断这两个相邻点是横向相邻还是纵向相邻。并分别将需要设立线段的位置(不同坐标的最小值)和相同坐标的出现次数存在两个数组中。然后按照相同坐标的出现次数从大到小排好序(这样也避免了会找到不需要设立线段的位置),然后横向取前K个需要设立线段的坐标(不满K个则输出所有需要的坐标),纵向同理。

当时做的时候也是这样想的,但是统计每一个需要设立线段的坐标和相同坐标的出现次数实在是太复杂了,WA，真的是欲哭无泪啊。。。。。。

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<queue>
#include<algorithm>
#include<cstring>
#define maxn 1005
using namespace std;
int M,N,K,L,D;
vector<int>a1,a2;
struct data
{
	int id,cnt;
	friend bool operator < (data a,data b)
	{
		return a.cnt>b.cnt;
	}
};
data a[maxn],b[maxn];
int main()
{
	//freopen("seat.in","r",stdin);
	//freopen("seat.out","w",stdout);
	
	scanf("%d%d%d%d%d",&M,&N,&K,&L,&D);
 
	for(int i=1;i<=D;i++)
	{
		int x,y,p,q;
		scanf("%d%d%d%d",&x,&y,&p,&q);
		if(x==p){b[min(y,q)].cnt++;b[min(y,q)].id=min(y,q);}
		if(y==q){a[min(x,p)].cnt++;a[min(x,p)].id=min(x,p);}
	}
	
	sort(a+1,a+maxn);
	sort(b+1,b+maxn);
	
	for(int i=1;i<=K;i++)
	{
		if(a[i].id>0)a1.push_back(a[i].id);
	}
	sort(a1.begin(),a1.end());
	
	for(int i=0;i<a1.size();i++)
	printf("%d ",a1[i]);
	
	printf("\n");
	
	for(int i=1;i<=L;i++)
	{
		if(b[i].id>0)a2.push_back(b[i].id);
	}
	sort(a2.begin(),a2.end());
	
	for(int i=0;i<a2.size();i++)
	printf("%d ",a2[i]);
	
	return 0;
}


来源：cqyz_yuyuko