審題：
本題需要我們找到最佳的排座椅方案，并輸出行，列方案

思路：
方法一：簡單貪心

由于題目會告訴我們有哪幾對的同學會交頭接耳，所以我們可以記錄下第幾行/第幾列上可以隔開的同學對數，而題目限制我們的行隔離只有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 普及組] 排座椅 - 洛谷