本题为错题,不存在复杂度正确的解法,然而我们高贵的洛谷题解区却有一篇非常简洁的题解。
让我们来拜读一下这篇题解,
一道标准的贪心问题(注:本题其实是 NP 问题)。 对于顶层,如果超出承重,就漏向底层称重少的那一个,并减少该层承重,看看底层会不会漏就好了。 证明: 对于最顶层的麦子,若其超过金字塔承重(ai>q1ia_i > q_{1i}ai>q1i),那么就要使它尽可能往下掉,故流向承重小的即为最优解。注:本篇不提供代码! 求关
题解作者也没有 AC 这道题目,请求撤下题解并直接封禁专栏以示警告。