洛谷 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\) 表示这个函数的答案，则可以列出方程：
经过一通计算，可得 \(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);
}