排座椅P1056 [NOIP 2008 普及组] 排座椅 - 洛谷题目详情算法原理性质横向的通道是不影响纵向通道的摆放的横纵通道是可以分开来考虑的。处理横向通道(纵向同理)收集每一行如果放上通道之后会解决多少个交头接耳的同学对收集的信息从大到小排序选最大的k行就是最优结果注意输出的结果下标需要从小到大输出。本题其实是不需要证明的我们都把最大的k个拿出来了如果还不是最优的话找谁说理去。代码实现#include iostream #include algorithm using namespace std; const int N 1010; int m, n, k, l, d; struct node { int index; int cnt; }row[N], col[N]; // 按照cnt从大到小排序 bool cmp1(node x, node y) { return x.cnt y.cnt; } // 按照index从小到大排序 bool cmp2(node x, node y) { return x.index y.index; } int main() { 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; while(d--) { int x, y, p, q;cin x y p q; if(x p) col[min(y, q)].cnt; else row[min(x, p)].cnt; } // 对两个数组按照 cnt 从大到小排序 sort(row 1, row 1 m, cmp1); sort(col 1, col 1 n, cmp1); // 对 row 数组前 k 个元素按照下标从小到大排序 sort(row 1, row 1 k, cmp2); // 对 col 数组前 l 个元素按照下标从小到大排序 sort(col 1, col 1 l, cmp2); 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; return 0; }结语如果觉得有收获欢迎点赞/收藏我们下期见