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

CloverArmeriaThrift · 2025-01-11 22:15:19 · 题解

在博客内阅读效果更加哦~

题目大意

题目传送门——原题面链接

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

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

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

• 首先，选出两个米糕 A 和 B，设其大小分别为 a 和 b。
• 如果 a \le \frac{b}{2}，那么 A 可以堆在 B 的上面，它们形成了一块“堆叠式米糕”。

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

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

• 所有米糕中，可以选择 2 \cdot K 块形成 K 个“堆叠式米糕”。

  思路

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

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

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

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

代码

Submission #61583414

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