【题解】AT_abc388_e AtCoder Beginner Contest ABC388 E Simultaneous Kagamimochi

建议阅读本次比赛 C 题题面。

有 $N$ 块米糕，按大小升序排列，第 $i$ 块米糕的大小为 $A_i$。

现在定义“堆叠式米糕”如下：

现在，问最多同时组成多少块“堆叠式米糕”。

具体地，要找出一个尽可能大的非负整数 $K$ 满足如下条件：

不会二分答案的读者推荐学习二分查找及贪心相关内容，本篇题解限于篇幅不再过多讲解。

看到这样套路化的问法，我们可以想到一种算法——二分答案。也就是说，我们要通过二分的方式，迅速地找到答案。

每一次，我们折半得到一个整数 $mid$，然后使用一个基于贪心构造的函数来检查它是否满足题意。如果满足，我们把左边界设为 $mid$，向右寻找更大的答案；如果不满足，那么更大的答案显然也不满足，所以我们把右边界设为 $mid - 1$，向左寻找合法答案。我们重复此过程直到答案值域缩小到一个数，此时这个数就是最终的答案。

接下来，让我们来看一看这个检查函数怎么写。首先，大家思考一个问题——较小的那个米糕要选哪些呢？显然，为了确保不会漏下任何可能，一定要选最小的那些！选择哪些米糕不重要，重要的是我们要贪心地判断该答案是否可行。然后思考较大的米糕——显然，小的较小米糕匹配小的较大米糕，未雨绸缪，以备后患，避免直接取最大的后面会没得选。还有一个小细节，我们要避免重复选择。这里实现方式不唯一，大家自行思考吧。

自认为这个方法是代码较为简短，思路较为简单清晰的一个做法，时间复杂度 $O(n \cdot log n)$。如果各位大神有更优做法，欢迎在评论区提出或私信讨论！