P1056 [NOIP 2008 普及组] 排座椅

题目简介题目分析由此可见这是一道贪心题。由题意可得我们会发现⼀些性质1.设置横向通道的时候并「不影响」左右相邻的同学2.设置纵向通道的时候并「不影响」上下相邻的同学。因此我们可以「分开」处理横向通道和纵向通道。处理横向通道纵向同理就不多赘述1.收集每⼀⾏如果放上通道之后会解决多少个交头接⽿的同学2.对收集的信息「从⼤到⼩」排序选最⼤的 k ⾏就是最优结果。不需要证明了吧......我们都把最⼤的 k 个拿出来了如果还不是最优的话找谁说理去。分析到这很明显找到最优解的策略非常简单所以不对劲在代码实现上会有一些困难不多说上代码。代码实现#includebits/stdc.h using namespace std; const int N 1e410; struct node { int index; int cnt; }row[N],col[N]; int m,n,k,l,d; // 按照 cnt 从⼤到⼩排序 bool cmp1(node x,node y) { return x.cnty.cnt; } // 按照 index 从⼩到⼤排序 bool cmp2(node x,node y) { return x.indexy.index; } int main() { cinmnkld; // 初始化结构体数组 for(int i1;im;i)row[i].indexi; for(int i1;in;i)col[i].indexi; while(d--) { int x,y,p,q; cinxypq; if(xp) col[min(y,q)].cnt; else row[min(x,p)].cnt; } // 对两个数组按照 cnt 从⼤到⼩排序 sort(row1,rowm1,cmp1); sort(col1,coln1,cmp1); // 对 col 数组前 l 个元素按照下标从⼩到⼤排序 sort(row1,row1k,cmp2); sort(col1,col1l,cmp2); //在这里的四个sort其实是两个大家可以在纸上模拟一下 //第一次排序按价值从高到低选出最好的 k 行和 l 列 //第二次排序按编号从小到大输出题目要求 for(int i1;ik;i) { coutrow[i].index ; } coutendl; for(int i1;il;i) { coutcol[i].index ; } coutendl; return 0; }