有没有房建设计的网站,阿里云主机上传网站,怎么样管理网站,电子商务网站建设第二版论文上课的时候总有一些同学和前后左右的人交头接耳#xff0c;这是令小学班主任十分头疼的一件事情。不过#xff0c;班主任小雪发现了一些有趣的现象#xff0c;当同学们的座次确定下来之后#xff0c;只有有限的D对同学上课时会交头接耳。
同学们在教室中坐成了 M 行 N 列这是令小学班主任十分头疼的一件事情。不过班主任小雪发现了一些有趣的现象当同学们的座次确定下来之后只有有限的D对同学上课时会交头接耳。
同学们在教室中坐成了 M 行 N 列坐在第 i 行第 j 列的同学的位置是ijijij为了方便同学们进出在教室中设置了 K 条横向的通道LLL 条纵向的通道。
于是聪明的小雪想到了一个办法或许可以减少上课时学生交头接耳的问题她打算重新摆放桌椅改变同学们桌椅间通道的位置因为如果一条通道隔开了两个会交头接耳的同学那么他们就不会交头接耳了。
请你帮忙给小雪编写一个程序给出最好的通道划分方案。在该方案下上课时交头接耳的学生对数最少。
输入描述:
第一行有 5 各用空格隔开的整数分别是 MNKLD2≤NM≤10000≤KM0≤LND≤2000MNKLD2 ≤ NM ≤ 10000 ≤ K M0 ≤ L ND ≤ 2000MNKLD2≤NM≤10000≤KM0≤LND≤2000。
接下来 DDD 行每行有 4 个用空格隔开的整数第 iii 行的 4 个整数 XiYiPiQiX_iY_iP_iQ_iXiYiPiQi表示坐在位置 (Xi,Yi)(X_i,Y_i)(Xi,Yi) 与 (Pi,Qi)(P_i,Q_i)(Pi,Qi) 的两个同学会交头接耳输入保证他们前后相邻或者左右相邻。输入数据保证最优方案的唯一性。
输出描述: 共两行
第一行包含 K 个整数a1a2……aK表示第 a1 行和 a11 行之间、第 a2 行和第 a21 行之间、…、第 aK 行和第 aK1 行之间要开辟通道其中 aiai1每两个整数之间用空格隔开行尾没有空格。 第二行包含 L 个整数b1b2……bk表示第 b1b_1b1 列和 b11 列之间、第 b2 列和第 b21 列之间、…、第 bL 列和第 bL1 列之间要开辟通道其中 bibi1每两个整数之间用空格隔开行尾没有空格。
示例1
输入
4 5 1 2 3
4 2 4 3
2 3 3 3
2 5 2 4
输出
2
2 4
说明 上图中用符号*、※、 标出了3对会交头接耳的学生的位置图中3条粗线的位置表示通道图示的通道划分方案是唯一的最佳方案。 对于横向和纵向分别进行贪心
#includebits/stdc.h
using namespace std;
int x[1010],y[1010];
int id[1010];
vectorint v;
bool cmpx(int a,int b)
{return x[a]x[b];
}
bool cmpy(int a,int b)
{return y[a]y[b];
}
int main()
{int n,m,k,l,d;cinnmkld;while(d--){int x1,y1,x2,y2;cinx1y1x2y2;if(x1x2)y[min(y1,y2)];else if(y1y2)x[min(x1,x2)];}for(int i1;in;i)id[i]i;sort(id1,id1n,cmpx);v.clear();for(int i1;ik;i)v.push_back(id[i]);sort(v.begin(),v.end());for(auto itv.begin();it!v.end();it)cout*it ;coutendl;for(int i1;im;i)id[i]i;sort(id1,id1m,cmpy);v.clear();for(int i1;il;i)v.push_back(id[i]);sort(v.begin(),v.end());for(auto itv.begin();it!v.end();it)cout*it ;coutendl;return 0;}
