算法题（148）：排座椅

审题：
本题需要我们找到最佳的排座椅方案，并输出行，列方案

思路：
方法一：简单贪心

由于题目会告诉我们有哪几对的同学会交头接耳，所以我们可以记录下第几行/第几列上可以隔开的同学对数，而题目限制我们的行隔离只有k行，列隔离只有l行，所以我们只要求出同学对数最多的前k行与前l列即可。

注意：我们最终输出的是行号/列号，若直接使用普通数组来记录数据会导致最后无法得知原本他们的行号/列号，所以我们使用结构体来进行数据记录

解题：

（1）结构体定义

struct sit
{int index;int count;
}row[N], col[N];

index就是行号/列号，count表示同学对数，row[N]是行结构体数组,col[N]是列结构体数组

（2）数据录入

cin >> m >> n >> k >> l >> d;//初始化结构体for (int i = 1; i <= m; i++) row[i].index = i;for (int i = 1; i <= n; i++) col[i].index = i;//记录数据for (int i = 1; i <= d; i++){int x, y, p, q;cin >> x >> y >> p >> q;if (x == p)//同一行{col[min(y, q)].count++;}else//同一列{row[min(x, p)].count++;}}

我们先对行和列的数组进行索引的初始化，然后将可以隔离的同学对数记录进对应的行/列中。

若x==p，同学在同一行，此时我们需要用列来隔离，所以对min(y,q)的列count++

若y==q，同学在同一列，此时我们需要用行来隔离，所以对min（x，q）的行count++

（3）排序

	bool count_sort(sit& s1,sit& s2)
{return s1.count > s2.count;
}
bool index_sort(sit& s1, sit& s2)
{return s1.index < s2.index;
}//以count进行排序sort(row + 1, row + 1 + m, count_sort);sort(col + 1, col + 1 + n, count_sort);//对前k个多对的根据index进行排序sort(row + 1, row + 1 + k, index_sort);//对前l个多对的根据index进行排序sort(col + 1, col + 1 + l, index_sort);

我们先根据count进行排序，count大的就排前面。

然后由于最后输出的时候要按照行号/列号小的排前面输出，所以我们再对排序后的前k行的行号进行排序，列也是同理。

（4）输出数据

//输出数据for (int i = 1; i <= k; i++){cout << row[i].index << " ";}cout << endl;for (int i = 1; i <= l; i++){cout << col[i].index << " ";}cout << endl;

P1056 [NOIP 2008 普及组] 排座椅 - 洛谷