acgo题库
  • 首页
  • 题库
  • 学习
  • 天梯
  • 备赛

    竞赛

    • CSP-J/S
    • 蓝桥杯

    考级

    • GESP
    • CPA
    • 电子学会考级
  • 竞赛
  • 讨论
  • 团队
登录
注册
题目详情提交记录(0)
  • 出题人题解|完美储存

    【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)

    userId_undefined

    复仇者_澜(不处不加团队)

    出道萌新秩序白银出题人
    35阅读
    0回复
    2点赞
暂无数据

提交答案之后,这里将显示提交结果~

首页