本文主要是介绍【NOIP2008普及组复赛】 题2:排座椅,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题2:排座椅
( s e a t . p a s / c / c p p ) (seat.pas/c/cpp) (seat.pas/c/cpp)
# 【题目描述】
上课的时候总有一些同学和前后左右的人交头接耳,这是令小学班主任十分头疼的一件事情。不过,班主任小雪发现了一些有趣的现象,当同学们的座次确定下来之后,只有有限的 D D D对同学上课时会交头接耳。同学们在教室中坐成了 M M M行 N N N列,坐在第i行第j列的同学的位置是( i , j i,j i,j),为了方便同学们进出,在教室中设置了 K K K条横向的通道, L L L条纵向的通道。于是,聪明的小雪想到了一个办法,或许可以减少上课时学生交头接耳的问题:她打算重新摆放桌椅,改变同学们桌椅间通道的位置,因为如果一条通道隔开了两个会交头接耳的同学,那么他们就不会交头接耳了。
请你帮忙给小雪编写一个程序,给出最好的通道划分方案。在该方案下,上课时交头接耳的学生的对数最少。
# 【输入文件】
输入文件 s e a t . i n seat.in seat.in的第一行,有 5 5 5个用空格隔开的证书,分别是 M , N , K , L , D M,N,K,L,D M,N,K,L,D ( 2 ≤ N , M ≤ 1000 , 0 ≤ K < M , 0 ≤ L < N , D ≤ 2000 ) (2≤N,M≤1000,0≤K<M,0≤L<N,D≤2000) (2≤N,M≤1000,0≤K<M,0≤L<N,D≤2000)。
接下来 D D D行,每行有 4 4 4个用空格隔开的整数。第 i i i行的 4 4 4个证书 X i , Y i , P i , O i X_i,Y_i,P_i,O_i Xi,Yi,Pi,Oi,表示坐在位置( X i , Y i X_i,Y_i Xi,Yi)与( P i , O i P_i,O_i Pi,Oi)的两个同学会交头接耳(输入保证他们前后相邻或者左右相邻)。
输入数据保证最优秀方案的唯一性。
# 【输出文件】
输出文件 s e a t . o u seat.ou seat.ou共两行。
第一行包含 K K K个整数, a 1 , a 2 … … a k a_1,a_2……a_k a1,a2……ak,表示第 a 1 a_1 a1行和 a 1 + 1 a_1+1 a1+1行之间、第 a 2 a_2 a2行和第 a 2 + 1 a_2+1 a2+1行之间、…、第a_K
行和第 a K + 1 a_K+1 aK+1行之间要开辟通道,其中 a i < a i + 1 ai<ai+1 ai<ai+1,每两个整数之间用空格隔开(行尾没有空格)。
第二行包含 L L L个整数, b 1 b 2 … … b L b_1b_2……b_L b1b2……bL,表示第 b 1 b_1 b1列和 b 1 + 1 b_1+1 b1+1列之间,第 b 2 b_2 b2列和 b 2 + 1 b_2+1 b2+1列之间、…、第 b L b_L bL列和第 b L + 1 b_L+1 bL+1列之间要开辟通道,其中 b i < b i + 1 b_i<b_i+1 bi<bi+1,每两个整数之间用空格隔开(行尾没有空格)。
# 【输入样例1】 seat.in
4 5 1 2 3
4 2 4 3
2 3 3 3
2 5 2 4
# 【输出样例1】 seat.ou
2
2 4
【输入输出样例解释】
上图中用符号 ∗ 、※, + *、※,+ ∗、※,+标出了 3 3 3对会交头接耳的学生的位置,图中3条粗线的位置表示通道,图示的通道划分方案是唯一的最佳方案。
【代码如下】:
#include <bits/stdc++.h>
using namespace std;
int M, N, K, L, D;
int x, y, p, q;
typedef struct tagINT {int ID;int entity;
} INT;
INT l[1020], t[1020], temp;
void save(int x, int y, int p, int q) {if (x == p) {l[min(y, q)].entity++;return;} else {t[min(x, p)].entity++;return;}
}
int main() {cin >> M >> N >> K >> L >> D;for (int i = 0; i < D; i++) {cin >> x >> y >> p >> q;save(x, y, p, q);}for (int i = 1; i <= M; i++) l[i].ID = i;for (int i = 1; i <= N; i++) t[i].ID = i;for (int i = 1; i <= M; i++) {for (int j = i + 1; j <= M; j++) {if (t[i].entity < t[j].entity) swap(t[i], t[j]);}}for (int i = 1; i <= N; i++) {for (int j = i + 1; j <= N; j++) {if (l[i].entity < l[j].entity) swap(l[i], l[j]);}}for (int i = 1; i <= K; i++) {for (int j = i + 1; j <= K; j++) {if (t[i].ID > t[j].ID) swap(t[i], t[j]);}}for (int i = 1; i <= L; i++) {for (int j = i + 1; j <= L; j++) {if (l[i].ID > l[j].ID) swap(l[i], l[j]);}}for (int i = 1; i <= K; i++) {if (i > 1) cout << ' ';cout << t[i].ID;}cout << endl;for (int i = 1; i <= L; i++) {if (i > 1) cout << ' ';cout << l[i].ID;}
}
这篇关于【NOIP2008普及组复赛】 题2:排座椅的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!