P1056 [NOIP 2008 普及组] 排座椅（贪心，排序）
题意
有 \(D\) 对同学上课时会交头接耳。同学们坐成 \(M\) 行 \(N\) 列，第 \(i\) 行第 \(j\) 列的位置是 \((i,j)\)，为了方便同学们进出，教室里有 \(K\) 条横向通道，\(L\) 条纵向通道。求出最好的通道划分方案。在该方案下，上课时交头接耳的学生的对数最少。
数据范围与约定
对于 \(100\%\) 的数据，保证：
\(2 \le N,M \le 1000;\)
\(0 \le K<M;\)
\(0 \le L<N,0\le D \le 2000\)。
题解
统计每个通道能分割的对数，选择最多的前 \(K\) 个或 \(L\) 个，对这 \(K\) 个或 \(L\) 个对位置进行升序排序即可（有点模拟的感觉）。
CODE
#include <bits/stdc++.h>
using namespace std;
/*====================*/
using ll=long long;
/*====================*/
#define endl '\n'
/*====================*/
int m, n, k, l, d;
/*====================*/
struct Unit
{int cut, pos;Unit(int cut_ = 0, int pos_ = 0){cut = cut_, pos = pos_;}
};
/*====================*/
const int N = 1e3 + 10;
/*====================*/
Unit cnt_row[N], cnt_col[N];
/*====================*/
bool Compare_1(const Unit& a, const Unit& b)
{return a.cut > b.cut;
} bool Compare_2(const Unit& a, const Unit& b)
{return a.pos < b.pos;
}
/*====================*/
void Solve()
{cin >> m >> n >> k >> l >> d;for (int i = 1; i <= d; i++){int x, y, p, q;cin >> x >> y >> p >> q;if (x == p){cnt_col[min(y, q)].cut++;}else{cnt_row[min(x, p)].cut++;}}for (int i = 1; i <= m - 1; i++){cnt_row[i].pos = i;}for (int i = 1; i <= n - 1; i++){cnt_col[i].pos = i;}sort(cnt_row + 1, cnt_row + m, Compare_1);sort(cnt_col + 1, cnt_col + n, Compare_1);vector<Unit> rows, cols;for (int i = 1; i <= k; i++){rows.push_back(cnt_row[i]);}for (int i = 1; i <= l; i++){cols.push_back(cnt_col[i]);}sort(rows.begin(), rows.end(), Compare_2);sort(cols.begin(), cols.end(), Compare_2);for (auto r : rows){cout << r.pos << " ";}cout << endl;for (auto c : cols){cout << c.pos << " ";}
}
/*====================*/
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);int T=1;//cin>>T;while(T--)Solve();return 0;
}