题解 | 排座椅

简单贪心。

显然，如果希望以有限的资源（有限数量的横纵向通道）尽可能杜绝“交头接耳”的现象，我们肯定优先选择布置效果尽可能优的通道。什么叫“效果尽可能优”呢？即一条通道隔绝“交头接耳”的学生对数尽可能多，我们就优先布置这条通道。用STL中相关容器+排序即可实现这一目的。

比较坑人的点在于输出也要求有序（莫名其妙），注意得到答案后再次排序即可。

#include<bits/stdc++.h>

using namespace std;

#define pb push_back
#define fi first
#define se second
#define endl '\n'
// ---
using ll=long long;
using ull=unsigned long long;
// ---
template<class K,class V>
using umap=unordered_map<K,V>;
template<class T>
using max_heap=priority_queue<T>;
template<class T>
using min_heap=priority_queue<T,vector<T>,greater<T>>;
// ---
// 创建随机引擎
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

// 生成一个在 [l, r] 间的随机整数
int randint(int l, int r) {
    uniform_int_distribution<int> dist(l, r);
    return dist(rng);
}

// 生成一个 [0,1) 的随机实数
double randdbl() {
    uniform_real_distribution<double> dist(0.0, 1.0);
    return dist(rng);
}
// ---
const int INF=1e9;
const ll  LINF=4e18; 
const int mod=1e9+7;
const double eps=1e-9; 
// ---
const int maxd=2e6+5;
int n,m,k,l,d;
vector<pair<int,int>> sr,sc;

bool cmp(pair<int,int> x,pair<int,int> y)
{
	return x.fi>y.fi;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin>>n>>m>>k>>l>>d;
	map<int,int> row,col;
	int x,y,p,q;
	for(int i=1;i<=d;++i)
	{
		cin>>x>>y>>p>>q;
		if(x==p)
			++col[min(y,q)];
		if(y==q)
			++row[min(x,p)];
	}
	for(auto it=row.begin();it!=row.end();++it)
	{
		int v1=(it->se),v2=(it->fi);
		sr.pb(make_pair(v1,v2));
	}
	for(auto it=col.begin();it!=col.end();++it)
	{
		int v1=(it->se),v2=(it->fi);
		sc.pb(make_pair(v1,v2));
	}
	sort(sr.begin(),sr.end(),cmp);
	sort(sc.begin(),sc.end(),cmp);
	vector<int> ansr,ansc;
	for(int i=1;i<=k && i<=sr.size();++i)	ansr.pb(sr[i-1].se);
	for(int i=1;i<=l && i<=sc.size();++i)	ansc.pb(sc[i-1].se);
	sort(ansr.begin(),ansr.end());
	sort(ansc.begin(),ansc.end());
	for(int i=0;i<ansr.size();++i)	cout<<ansr[i]<<' ';
	cout<<endl;
	for(int i=0;i<ansc.size();++i)	cout<<ansc[i]<<' ';
	return 0;
}