P8170 题解

· · 题解

这题跟 P3826 [NOI2017] 蔬菜 在外观上差不多，如果再深入观察一下，会发现跟蔬菜这道题恰好相反。

即：每棵树尽量在前面被砍，且当前能算出的答案最大的值最应该被砍。

对于一棵树，只有最终答案和什么时候能被砍这两个东西有意义，需要维护。

考虑一个 naive 的想法，二分一个答案 ans，枚举每天每棵树的状态，先把每棵高度超过 ans 的树砍到小于等于 ans，如果还能剩余一些砍树的机会，则优先砍当前最高的树（除非最高的树都小于 x，砍不了）。

这个想法错在哪里？对于一棵树并不是一比 ans 大就砍是最优的，因为如果它下一次大于 ans 时有很多很多树都同时大于 ans，就可能砍不到它。虽然硬构造这样一组数据很困难，但由于此题有子任务捆绑所以并不能通过，而且时间复杂度并不优秀。

但据此可以想到一个正确的二分答案做法，即对于所有最终要超过 ans 的树，当前能砍则砍，按最终高度从高到低砍，这样是能够让砍掉的利益最大化的，因为既然最后要超过 ans，那无论如何总得砍，能早砍就早砍。

还可以想到一个更 naive 的贪心的做法，把所有树直接转化成其最终高度，不考虑日期，然后 Mk 个操作每次选当前最高的树砍，用堆维护，时间复杂度 O(Mk\log N)。问题在于，有些树在有些日期是砍不了的。比如构造很多棵全都长得很慢的树，它们在最后一天同时高度超过了 x，如果这样贪心，可以在前面的日子里把最后的这些树给砍光，但由于它们全都在同一天长出来，所以是砍不完的。

问题就出在维护日期上。所以考虑给每棵树设一个限制：必须在第 day 天及之后才能砍，day 表示到第 day 天这棵树才长得大于等于 x，这是能砍的充分必要条件。

然而每次砍了一棵树，这棵树又可能会掉下 x 去，所以还要维护一个变量表示已经砍了几刀，目的是方便计算后续的 d。

考虑实现一个函数 Get(int h,int d,int c)，表示当前这棵树的初始高度为 h，每天长 d，已经被砍了 c 次，至少要第几天才能长得超过 x。

设 a 表示这个函数的答案，则可以列出方程：

h+ad-cx\geq x

经过一通计算，可得 a=\lceil \frac{(c+1)x-h}{d} \rceil。发现 d 为 0 的时候需要特判，因为越早砍越好，所以如果能砍，a=1，否则 a=\inf。 因为必须从第一天开始才能砍，所以最后 a 要和 1 取 \max。

按照之前的 naive 贪心原则，每次选当前计算出的最终高度最高的树，并把其剪掉，找出这棵树记录的 day 及之后的第一个可以用的剪树名额，用掉它，然后算出新的 day。

对于每次选最终高度更高的树，可以用堆维护，如何计算 day 及之后第一个可以用的剪树名额？有一个套路的做法，记录每天还能用的剪树个数 Cnt，用并查集维护其后 Cnt 不为 0 的第一天，如果当前用了这天的剪树次数之后 Cnt 为 0 了，往后合并就行。

时间复杂度 O(Mk\log N)，可以通过，但不够优秀。

若把所有树按照一次都不剪算出来的最终高度排序，每棵树如果都被剪了一次，在相对高度上是完全相同的，所以可以用队列维护被剪过的树（一定是单调队列），用数组初始排序维护最终高度从大到小没被剪过的树。

每次比对队列开头和数组当前位置，选择较大的一方进行操作，然后放入队列末尾。如果队列为空，直接用数组当前位置（当且仅当第一次操作才会出现这种情况）。否则如果用了数组当前位置，应以后用下一个位置（即数组每个下标只会被用一次，毕竟维护的是没有剪过的树）。

时间复杂度为 O(N \log N+Mk)。

堆的代码

队列的代码

以上两份代码的 Get 函数都写错了，正确写法应该是：

int Get(int h,int d,int c)
{
    if(d==0)
    {
        return h-c*X<X?M+1:1;
    }
    return max(1,((c+1)*X-h-1)/d+1);
}