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

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

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

Sum of Adjacent Minimums

返回题目

题解

다음 값을 생각하자.

M=max⁡1≤l<r≤Nr−lCl+Cl+1+⋯+Cr.M=\max_{1\leq l<r\leq N}\dfrac{r-l}{C_l+C_{l+1}+\cdots+C_r}.M=1≤l<r≤Nmax​Cl​+Cl+1​+⋯+Cr​.

정답은 XMXMXM이다. 따라서 누적합을 사용해 모든 구간 [l,r][l,r][l,r]을 확인하면 O(N2)O(N^2)O(N2)에 해결할 수 있다.

직관

처음부터 어떤 최적해가 다음과 같은 꼴이라고 예상해 보자.

0,⋯ ,0,H,H,⋯ ,H,0,⋯ ,00,\cdots,0,H,H,\cdots,H,0,\cdots,00,⋯,0,H,H,⋯,H,0,⋯,0

양수인 부분이 구간 이라면, 조건 에 의해 로 정해진다. 이때 목적함수의 값은 다음과 같다.

증명

임의의 가능한 R1,R2,⋯ ,RNR_1,R_2,\cdots,R_NR1​,R2​,⋯,R을 고정하자. 음이 아닌 실수 에 대해 인 인덱스 만 남겨 보자. 남은 인덱스들은 서로 겹치지 않는 여러 연속 구간으로 나뉜다.

Solution written by GPT5.6

r−l
​
[l,r][l,r]
[l,r]
C1R1+C2R2+⋯+CNRN=XC_1R_1+C_2R_2+\cdots+C_NR_N=XC1​R1​+C2​R2​+⋯+CN​RN​=X
H=XCl+Cl+1+⋯+CrH=\dfrac{X}{C_l+C_{l+1}+\cdots+C_r}H=Cl​+Cl+1​+⋯+Cr​X​
(r−l)H=Xr−lCl+Cl+1+⋯+Cr(r-l)H=X\dfrac{r-l}{C_l+C_{l+1}+\cdots+C_r}(r−l)H=XCl​+Cl+1​+⋯+Cr​r−l​

따라서 이러한 꼴의 해만 생각한다면 얻을 수 있는 최댓값은 XMXMXM이다.

N
​
ttt
Ri≥tR_i\geq tRi​≥t
iii

그중 하나가 [l,r][l,r][l,r]이라면, 이 구간에서 서로 이웃하게 남아 있는 인덱스 쌍은 r−lr-lr−l개이다. MMM의 정의에 의해 (r−l)≤M(Cl+Cl+1+⋯+Cr)(r-l)\leq M(C_l+C_{l+1}+\cdots+C_r)(r−l)≤M(Cl​+Cl+1​+⋯+Cr​)가 성립한다.

모든 연속 구간에 대해 더하면, 높이 ttt에서 동시에 남아 있는 이웃한 인덱스 쌍의 수는 M∑1≤i≤NRi≥tCiM\displaystyle\sum_{\substack{1\leq i\leq N\\R_i\geq t}} C_iM1≤i≤NRi​≥t​∑​Ci​ 이하이다.

높이 ttt에서 동시에 남아 있는 이웃한 인덱스 쌍의 수를 K(t)K(t)K(t)라고 하자. 각 (i,i+1)(i,i+1)(i,i+1)은 0≤t≤min⁡(Ri,Ri+1)0\leq t\leq\min(R_i,R_{i+1})0≤t≤min(Ri​,Ri+1​)인 동안 정확히 하나씩 세어지므로, 목적함수의 값은 ∫0∞K(t) dt\int_0^\infty K(t)\,dt∫0∞​K(t)dt이다. 따라서 위 부등식을 t≥0t\geq 0t≥0에 대해 적분하면

∫0∞K(t) dt≤M∫0∞∑1≤i≤NRi≥tCi dt=M∑i=1NCiRi=MX\begin{aligned} \int_0^\infty K(t)\,dt &\leq M\int_0^\infty \displaystyle\sum_{\substack{1\leq i\leq N\\R_i\geq t}} C_i\,dt \\ &=M\sum_{i=1}^{N}C_iR_i \\ &=MX \end{aligned}∫0∞​K(t)dt​≤M∫0∞​1≤i≤NR

를 얻는다.

이제 MMM을 만드는 구간 [l,r][l,r][l,r]을 하나 고르자. l≤i≤rl\leq i\leq rl≤i≤r인 모든 iii에 대해

Ri=XCl+Cl+1+⋯+CrR_i=\dfrac{X}{C_l+C_{l+1}+\cdots+C_r}Ri​=Cl​+Cl+1​+⋯+Cr​X​

로 두고, 나머지 RiR_iRi​를 000으로 둔다. 그러면 조건을 만족하며 목적함수의 값은 XMXMXM이다.

따라서 XMXMXM이 정확한 최댓값이다.

i
​
≥
t
​
∑
​
Ci​
d
t
=Mi=1∑N​Ci​Ri​
=MX
​