【ZSROI R1-B】完美储存
题目大意:
有若干硬盘,每个硬盘空间为 SSS。有 nnn 个文件,你需要依次处理他们,对于一个文件 iii,其需要 aia_iai 的空间。你一定会把这个文件放进当前剩余容量最大的硬盘内。求最少硬盘数使得空间不会溢出且所有文件均能存储。
20pts:20pts:20pts:
暴力全过程。
40pts:40pts:40pts:
见下文满分代码,仅使用一个优化可以得到。
100pts:100pts:100pts:
* 优化一:
因为 ai≤Sa_i\le Sai ≤S,所以最坏情况下只需要 nnn 个硬盘,换句话说就是 nnn 个硬盘肯定可以,那么即答案具有单调性,于是考虑二分硬盘个数,优化掉一重循环。
* 优化二:
对于每个 aia_iai 要找剩余最大的硬盘,用优先队列维护当前最大硬盘即可。
时间复杂度:O(Tnlog2n)O(Tnlog^2n)O(Tnlog2n)