Educational Codeforces Round 110 Gold Transfer 题解 (C++ only)

题解

首先,因为子节点的cost一定高于其父亲节点。因此显而易见的,我们会优先选择深度更低的节点。于是我们立刻想到要快速的找到深度最浅且仍有剩余黄金的节点。

于是我们很自然的想到二分的方式。以一个深度为9的节点为例,倍增的建立一个其祖先节点位置的索引:

假如1号节点没有黄金且5号节点有黄金。但由于不知道2-4号的节点是否有黄金,因此我们从5号节点出发继续找:

以此类推,我们可以O(logn)的得到深度最浅的有黄金的节点。然后我们在这个节点尽可能多的购买。如果不够就再重新从9号节点做一次即可。

至于为什么这样不会超时呢?因为我们可以发现,对于一次购买,最坏的情况是:某一个节点买了一部分,但这个节点的所有父亲全部都被买空。
因此,一旦某个子节点空了,则其所有父亲节点一定是空的。因此虽然我们会多次找最浅的节点,但除了最后一次,其他的重复在整个查询过程中只会出现一次(因为这一次过后,就一定是0,不再出现)。

代码

C++

Submission #118491220 - Codeforces
Codeforces. Programming competitions and contests, programming community

Java

TLE在26组。但其实完全和我的C++代码是完全同样的做法,但C++过了。

Submission #118490612 - Codeforces
Codeforces. Programming competitions and contests, programming community
展示评论