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

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

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

짐비의 사냥

返回题目

题解

단일 공격 직후에 광역 공격을 사용한다면, 두 공격의 순서를 바꾸어도 다른 몬스터가 받는 피해는 같다. 순서를 바꾼 뒤 단일 공격의 대상이 이미 처치되었다면 그 단일 공격은 생략할 수 있다. 따라서 광역 공격을 모두 먼저 사용하고, 남은 몬스터를 단일 공격으로 처치하는 최적의 방법이 존재한다.

광역 공격을 KKK번 사용하면 체력이 KKK 이하인 몬스터가 모두 처치된다. 따라서 필요한 공격 횟수는 다음과 같다.

f(K)=K+∣{i∣1≤i≤N, Hi>K}∣.f(K)=K+\left|\{i\mid 1\leq i\leq N,\ H_i>K\}\right|.f(K)=K+∣{i∣1≤i≤N, Hi​>K}∣.

KKK가 000보다 크고 어떤 몬스터의 초기 체력과도 같지 않다면, KKK를 111 줄여도 남는 몬스터의 수가 같다. 그러므로 K=0K=0K=0 또는 K=HiK=H_i인 경우만 확인하면 된다.

체력을 오름차순으로 정렬하여 A1≤A2≤⋯≤ANA_1\leq A_2\leq\cdots\leq A_NA1​≤A2​≤⋯≤A이라 하자. 일 때의 공격 횟수 을 초기 정답으로 둔다. 각 서로 다른 체력의 마지막 위치 에 대해 를 계산하여 정답을 갱신한다. 시간 복잡도는 , 공간 복잡도는 이다.

또한 정답은 단일 공격만 사용하는 경우의 횟수인 NNN 이하이므로, 0≤K≤N0\leq K\leq N0≤K≤N만 확인해도 된다. 체력이 NNN 이하인 몬스터의 수를 체력별로 세어 두면 O(N)O(N)O(N) 시간에도 풀 수 있다.

Solution written by GPT6

K
=
Hi​
N
​
K=0K=0K=0
NNN
iii
Ai+N−iA_i+N-iAi​+N−i
O(Nlog⁡N)O(N\log N)O(NlogN)
O(N)O(N)O(N)