有意思的贪心+二分好题

· · 题解

坏了，这种绿做不出了。

本文不会滥用“注意到”“考虑”“显然”“容易”“易证”“易得”“发现”等不良词汇。

读完题目的第一反应是有太多的分配情况，DP 不行，贪心感觉行但是不会贪心策略。

那么不会贪心策略的原因就是题目的信息量过于少。由于方案的不同，我们最终的答案也就不同。如果说我们考虑让两个人尽可能大，同时顾虑到行数比自己小的人列比自己小，每个人都要有座位的话，我们时不好分配座位的。

但是题目没有让我们求每一个人的坐标，换言之我们并不需要知道每一个人的位置。所以我们不妨枚举这个最大乘客总满意度。这个满意度其实就是距离的下界。对于每一个乘客，尽可能往这个矩阵的左边放。看是否能放下。能优先处理列小的原因是我们可以保证它的行更新，依次处理让每一组的行迭代更新。

我们应该思考的是如何完成检查这个最大乘客总满意度是否合法这个任务。

首先，题目告诉了我们每个人需要的列。然后题目说了行数比自己小的人列比自己小，每个人都要有座位的话，我们时不好分配座位的。那么我们不妨优先处理列比较小的。对于这些列比较小的人而言，我们优先安排行数小的。这样后面的人就更有可能能够安排的下。

那么此时我们就得出了两个约束条件：

根据距离就是列差加上行差，我们能知道行的差，因此我们能计算出当前行的位置。当然得和上一次的行取最大值。

不合法就是说我们的行超过了题目给的 h 行。

如果当前是第 x 列，第一个人在第 st 行，有 p 个人，那么当前这一列的最后一个人就在第 st+(p-1) \times dist。dist 是我们距离的下界。

时间复杂度：O(N \log n)。

逻辑就应该很清晰了吧。