DOJ logoDOJ
题目
最近添加的题目收藏的题目Workbooks
分类DLC比赛小组团队讨论区
排名
解题数量排行榜连续解题排名DOJ Power 排行榜
评测状态
征题登录注册
DOJ logoDOJ

支持 OI 子任务计分、Elo 等级分和 Discord 账号绑定的社区在线评测系统。

题目
题目列表分类
社区
比赛排名讨论区公告举办外部比赛指南
账号
登录注册评测状态
政策
服务条款DLC 使用规则隐私政策API 文档语言运行环境比赛排名奖励评级与表现
© 2026 DOJ
保留所有权利
题解

攻略地下城

返回题目

题解

当前等级为 XXX 时,只需考虑满足 Ai<XA_i < XAi​<X 的地下城。挑战不满足该条件的地下城不会提升等级,因此不可能优于之后再挑战该地下城。

在满足 Ai<XA_i < XAi​<X 的地下城中,选择 BiB_iBi​ 最小的地下城。若当前等级为 XXX,所选地下城的第二个难度值为 BBB,则攻略后的等级为

X+min⁡(X,B)X+\min(X,B)X+min(X,B)

。

设当前可以攻略的两个地下城的第二个难度值满足 b≤cb \leq cb≤c,则按照 b,cb,cb,c 的顺序攻略这两个地下城后得到的等级,不小于按照 c,bc,bc,b 的顺序攻略后得到的等级。反复应用这一交换论证可知,优先选择当前可以攻略的地下城中 BiB_iB 最小的地下城,不会失去最优解。

将地下城按照 AiA_iAi​ 升序排序。把所有满足 AiA_iAi​ 小于当前等级的地下城的 BiB_iB 加入最小堆,然后从堆中取出最小值并更新等级。如果堆为空,则剩余的所有地下城都无法使等级提升,因此结束算法。

时间复杂度为 O(Nlog⁡N)O(N\log N)O(NlogN),空间复杂度为 O(N)O(N)O(N)。最终等级不超过 L+∑BiL+\sum B_iL+∑B,因此不超过 ,处于有符号 64 位整数的取值范围内。

Solution written by GPT5

i
​
i
​
i
​
5.00001×10175.00001\times 10^{17}5.00001×1017