排座椅-题解

题目要求输出 设置横列通道使得"交头接耳"的学生对数最少 的方案
对于最优化方案可以看出是贪心

但是贪心的策略是什么？

很显然要让通道穿过尽可能多的会讲话的同学对
即每次选择 排/列 可隔开人数数量最多的那个，选k/l次

可又但是我们如何实现这个贪心呢？？

可以创建结构体数组，数组内存储两个值 1.若设置这个通道可以隔开学生的数量 2.这个为第几 行/列 的通道(Id)
而后进行排序，排序后输出前k和l个数据就行了

可又双叒但是，如何去证明这个贪心呢？？？

如果你的贪心策略找不出反例，那么这个思路大概就是对的awa

#include<bits/stdc++.h>
using namespace std;
int m,n,k,l,d;//M行N列,设K横道,设L纵道,D对同学 
struct SZ{int sum=0;int id;};//通道结构体 
SZ sz_p[1005];//存储 若该排上设置通道 则可以隔开多少对学生 
SZ sz_l[1005];//存储 若该列上设置通道 则可以隔开多少对学生 
bool cmp1(SZ x,SZ y){return x.sum>y.sum;}//排序可以隔开的人数,可以隔开多的在前面(最优解)
bool cmp2(SZ x,SZ y){return x.id<y.id;}//坑点：排序Id,行/列数小的在前,因为输出要去小的在前
int main() {
	cin>>m>>n>>k>>l>>d;
	for(int i=1;i<=d;i++){
		int x,y,p,q;
		cin>>x>>y>>p>>q;//这里的x,y没用,但依旧要输入一下QwQ
		//如果x轴上的不一样则代表,处于同一列不同排 存储到列sz_p数组内
		//如果y轴上的不一样则代表,处于同一排不同列 存储到列sz_l数组内
		if(x!=p&&y==q){sz_p[min(x,p)].sum+=1;sz_p[min(x,p)].id=min(x,p);} 
		else if(x==p&&y!=q){sz_l[min(y,q)].sum+=1;sz_l[min(y,q)].id=min(y,q);}
	}
	//开始排序 
	//先排序数值
    sort(sz_p****z_p+1001,cmp1);
	sort(sz_l****z_l+1001,cmp1);
	//再排序ID(输出要求)
    sort(sz_p****z_p+k+1,cmp2);
	sort(sz_l****z_l+l+1,cmp2);
	//直接输出前k和l项,因为已经把最优的前k/l项排列好了 
    //I AK YuiliceOI~~~ (不是 
	for(int i=1;i<=k;i++){cout<<sz_p[i].id<<' ';}cout<<endl;
	for(int i=1;i<=l;i++){
		cout<<sz_l[i].id<<' ';
	} 
	return 0;
}

一道贪心题，虽然标签打的贪心，但是觉得这个贪心不太凸显，即使没学过算法的也能很容易想到思路！
不过这道题在隔壁打了黄，有点Water~