蓝桥杯备考：贪心算法之排座位

这道题横着放和竖着放之间是不会产生影响的

我们先说一下算法原理：我们先把所有行能阻止交头接耳的学生数量计算出来，再把每列的计算出来，然后再排一下序，按编号输出最大的几个，但是如果我们用数组存这些数据的话，排完序之后编号就乱了，所以我们选择结构体存储

我们输入的同学的坐标，如果横坐标相同的时候，就说明他们是横着呆着的，我们要在纵列放一个通道，如果纵坐标相同的时候，我们要横着放通道

#include <iostream> #include <algorithm> const int N = 1010; using namespace std; struct node { int id; int cnt; }col[N], row[N]; int n, m, k, l, d; bool cmp1(const node& x1, const node& x2) { return x1 t > x2 t; } bool cmp2(const node& x1, const node& x2) { return x1.id < x2.id; } int main() { cin >> m >> n >> k >> l >> d; for (int i = 1; i <= m; i++) row[i].id = i; for (int j = 1; j <= n; j++) col[j].id = j; while (d--) { int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; if (x1 == x2) col[min(y1, y2)] t++; else row[min(x1, x2)] t++; } sort(col + 1, col + n + 1, cmp1); sort(row + 1, row + m + 1, cmp1); sort(col + 1, col + l + 1, cmp2); sort(row + 1, row + k + 1, cmp2); for (int i = 1; i <= k; i++) { cout << row[i].id << " "; } cout << endl; for (int j = 1; j <= l; j++) { cout << col[j].id << " "; } cout << endl; return 0; }