一道主席树的好题,虽然WA到哭, 但是最后再自己静下心来理一遍思路,还是很多地方值得学习的。
思路
根据题意我们可以很快算出X次Cut后,树木应该剩余的总的高度,但是我们不知道第X次应该从哪个高度去Cut,因此可以二分枚举这个高度,我们把序列用主席树建好,然后就可以查询小于当前高度的总的高度了,再加上高于当前高度的树木的个数 * 当前高度 就是 总的剩余的高度了,我们把这个和理论值比较即可二分。注意Long long 和double的问题。另外本题不需要离散化,因为最大的高度才100000,因此我们可以直接根据高度值建树。
1 |
|