[BZOJ2527/Luogu3527][POI2011]Meteors(整体二分)

发布于 2018-04-17  5 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ2527/Luogu3527][POI2011]Meteors(整体二分)

Description

Byteotian Interstellar Union有N个成员国。现在它发现了一颗新的星球,这颗星球的轨道被分为M份(第M份和第1份相邻),第i份上有第Ai个国家的太空站。
这个星球经常会下陨石雨。BIU已经预测了接下来K场陨石雨的情况。
BIU的第i个成员国希望能够收集Pi单位的陨石样本。你的任务是判断对于每个国家,它需要在第几次陨石雨之后,才能收集足够的陨石。

Tag

整体二分

解决思路

对于每一个国家,二分答案。每一次算到当前二分时间的mid,然后将已经满足的国家归到左边处理,还未满足的国家归到右边处理。
为了方便处理最后收集不满的国家,可以在最后面再加一个为inf的陨石雨,方便所有国家都收集满。
至于每一次陨石雨的计算,可以用树状数组来维护。

代码

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ2527/Luogu3527][POI2011]Meteors(整体二分)


HNCJ OIer 一枚