Editorial

---

D

문제 요약:

\(b_i = \lfloor {i \over a_i} \rfloor\)인 $b_i$가 주어진다. 모든 i에 대해 $a_i$를 구하라.

문제 해설:

식을 정리해 보면 \({i \over {b_i + 1} } < a_i \leq {i \over b_i}\) 가 되는데,

\(1 ... n\)까지의 $a_i=x$에 대해 위의 식으로 만들어지는 구간을 하나씩 할당해야 한다.

$b_i$와 $i$만 있으면 $a_i=x$가 가능한 구간이 만들어진다.

$x$가 1부터 $n$까지 돌건데,

어떤 $i$에 의해 만들어지는 왼쪽 구간이 현재 $x$에 대해 가능한지 판별하기 위해 모든 구간들을 왼쪽 기준으로 정렬을 해 놓고(오른쪽 구간을 저장할 필요는 없음, 대신 오른쪽 구간의 정보를 알아내기 위해 i의 정보는 같이 저장되어야 한다)

현재 가능한 $i$에 대해($x$가 왼쪽구간보다 큰지 판단) 만들어지는 가장 작은 오른쪽 구간을 가지는 $i$의 $a_i$를 $x$로 정하면 된다.(set으로 구현)