排座椅【牛客tracker 每日一题】
排座椅
时间限制：1秒 空间限制：50M
知识点：贪心
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
教室内共有n nn行m mm列座位，坐在第i ii行第j jj列同学的位置记为( i , j ) (i,j)(i,j)。
为了方便进出，班主任计划设置k kk条横向通道（贯穿整列的水平通道）与l ll条纵向通道（贯穿整行的竖直通道）。通道位于相邻两行（或两列）之间。
班主任记录了d dd对经常交头接耳的同学，他们的位置( x i , y i ) (x_i,y_i)(xi,yi)与( p i , q i ) (p_i,q_i)(pi,qi)保证相邻（上下或左右）。她希望通过合理放置通道，使尽可能多的"交头接耳"对被通道隔开。
现请你输出唯一的最优方案，在该方案下，仍未被通道隔开的"交头接耳"对的数量最少。
输入描述：
第一行输入五个整数n , m , k , l , d ( 2 ≦ n , m ≦ 1 0 3 ; 0 < k < n ; 0 < l < m ; 0 < d ≦ 2 × m i n n,m,k,l,d(2≦n,m≦10^3; 0<k<n; 0<l<m; 0<d≦2×minn,m,k,l,d(2≦n,m≦103;0<k<n;0<l<m;0<d≦2×min{n × m , 2 × 1 0 3 n×m,2×10^3n×m,2×103}) ))。
接下来d dd行，每行输入四个整数x i , y i , p i , q i x_i,y_i,p_i,q_ixi,yi,pi,qi，表示坐标( x i , y i ) (x_i,y_i)(xi,yi)与( p i , q i ) (p_i,q_i)(pi,qi)的两位同学会交头接耳，且两坐标上下相邻或左右相邻。
保证最优方案存在且唯一。
输出描述：
第一行输出k kk个严格递增的整数a 1 , a 2 , … , a k ( 1 ≦ a 1 < ⋯ < a k ≦ n − 1 ) a_1,a_2,…,a_k(1≦a_1<⋯<a_k≦n−1)a1,a2,…,ak(1≦a1<⋯<ak≦n−1)，在行a i a_iai与a i + 1 a_{i+1}ai+1之间设置横向通道。
第二行输出l ll个严格递增的整数b 1 , b 2 , … , b l ( 1 ≦ b 1 < ⋯ < b l ≦ m − 1 ) b_1,b_2,…,b_l(1≦b_1<⋯<b_l≦m−1)b1,b2,…,bl(1≦b1<⋯<bl≦m−1)，在列b i b_ibi与b i + 1 b_{i+1}bi+1之间设置纵向通道。
示例1
输入：
4 5 1 2 3 4 2 4 3 2 3 3 3 2 5 2 4输出：
2 2 4说明：
该样例如下图所示，蓝底斜线方格为第一对交头接耳的同学，绿底带叉方格为第二对交头接耳的同学，粉底带星方格为第三对交头接耳的同学。粗线代表通道。该划分方案为唯一最优方案。
示例2
输入：
2 2 1 1 4 1 1 1 2 1 1 2 1 2 1 2 2 1 2 2 2输出：
1 1解题思路
首先初始化两个结构体数组，分别记录纵向通道（列间）和横向通道（行间）的位置编号及能隔开的交头接耳对数，遍历每对交头接耳的同学，若两人左右相邻则累加对应列间位置的计数，若上下相邻则累加对应行间位置的计数；随后对纵向、横向计数数组按隔开对数降序排序，选取前l ll个纵向位置和前k kk个横向位置；再将选中的位置按编号升序排序，最终依次输出排序后的横向、纵向通道位置；该贪心策略优先选择隔开对数最多的位置，保证最大化隔开的交头接耳对，且因最优方案唯一，排序操作能精准得到结果，时间复杂度适配n nn、m ≤ 1 e 3 m≤1e3m≤1e3和d ≤ 2 e 3 d≤2e3d≤2e3的规模，高效构造出唯一的最优通道放置方案。
代码内容
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefpair<ll,ll>pii;constll p=1e9+7;constll N=5e2+20;structIDCnt{ll id=0,cnt=0;}cnt[2][1005];boolcmp1(IDCnt a,IDCnt b){returna.cnt>b.cnt;}boolcmp2(IDCnt a,IDCnt b){returna.id<b.id;}intmain(){ll n,m,k,l,d;cin>>n>>m>>k>>l>>d;for(ll i=1;i<=m;i++)cnt[0][i].id=i;for(ll i=1;i<=n;i++)cnt[1][i].id=i;for(ll i=0;i<d;i++){ll x,y,p,q;cin>>x>>y>>p>>q;if(x==p)++cnt[0][min(y,q)].cnt;else++cnt[1][min(x,p)].cnt;}sort(cnt[0]+1,cnt[0]+m,cmp1);sort(cnt[1]+1,cnt[1]+n,cmp1);sort(cnt[0]+1,cnt[0]+l+1,cmp2);sort(cnt[1]+1,cnt[1]+k+1,cmp2);for(ll i=1;i<=k;i++)cout<<cnt[1][i].id<<" ";cout<<endl;for(ll i=1;i<=l;i++)cout<<cnt[0][i].id<<" ";return0;}