11.[NOIP2008 普及组] 排座椅 难度：普及- 来源：NOIP提高组 AC & WA代码（C++）： 注释代码为WA代码，下面代码为AC代码，注释在WA代码中。 没有注释，自行学习。 by：ACGO 你的点赞和关注就是我更新题解的最大动力！ -----------------------------点个赞吧 ↓ ！-----------------------------

先定义两个数组x,y x[1]表示如果在第一列与第二列中间划分过道能够分开几组说话的同学,同理,x[2]则是第二列与第三列... 直到x[n-1] y[1]表示第一行与第二行，y[2]表示第二行与第三行... 直到y[m-1] 题目输入两个同学的坐标，如果横坐标相同，即这两个同学在一行，那么设两个同学纵坐标分别为a,b 如果a<b 那么x[a]++ 否则x[b]++（这里一定要特判一下a和b的大小） 同理 y数组也如此操作即可。 最后x,y数组分别扫一遍，然后桶排一下即可。

不多废话,上题解！！！

ac题解

话不多说，请看题解~

思路： 题目要求给定教室大小，可以分排/行的数量，会讲话的同学对数，求出分排/行的位置 根据题意，先输入n，m，l，k，d（PS：我用的n，m与l，k是反的，不影响结果） while输入d对讲话的同学的位置，因为这对同学必然在x，y上有一个不同，有一个相同，所以可以通过判断哪个相同，将另一部分的最小值所对应的数组位置加1，表示在这个位置分隔后能分开的同学对数加1 然后，遍历数组的两层，分别加入优先队列q1，q2，q1/q2是sum大的在前面，也就是可以分开的同学对数多的在前面，这样就能尽可能使分开的同学多一点 但是还没完，因为题目要求输出的是升序队列，也就是分隔的位置小的在前面，所以还得把q1的前l个，q2的前k个放入qq1，qq2，qq1/qq2是idx小的在前面，也就是分隔的位置小的在前面，再输出，我们就实现了升序输出，end 代码：

题目要求输出 设置横列通道使得"交头接耳"的学生对数最少 的方案 对于最优化方案可以看出是贪心 但是贪心的策略是什么？ 很显然要让通道穿过尽可能多的会讲话的同学对 即每次选择 排/列 可隔开人数数量最多的那个，选k/l次 可又但是我们如何实现这个贪心呢？？ 可以创建结构体数组，数组内存储两个值 1.若设置这个通道可以隔开学生的数量 2.这个为第几 行/列 的通道(Id) 而后进行排序，排序后输出前k和l个数据就行了 可又双叒但是，如何去证明这个贪心呢？？？ 如果你的贪心策略找不出反例，那么这个思路大概就是对的awa 一道贪心题，虽然标签打的贪心，但是觉得这个贪心不太凸显，即使没学过算法的也能很容易想到思路！ 不过这道题在隔壁打了黄，有点Water~

™的，我调了好几天

代码如下：简单明了