KOI 2013 - 전봇대

https://www.acmicpc.net/problem/8986

문제 한줄요약 :

를 최소로 하는 x를 구하시오.

x를 이진탐색 할 수 있다면 N * lg1e9에 구할 수 있다.

그래서 아무 생각없이 이진탐색한다음에 내면 accept 먹일 수 있는데

그러라고 낸 문제가 아닐테니, 제대로 해보자.

좌표평면에 저걸 쫙 그려보면 x축과 a[i]/i에서 만나는 직선들이 수두룩하게 쌓여 있을 것이다.

저 직선들의 합의 극소값이 하나만 있다는 걸 보이면 된다.

직선들을 싹 더해보자.

-inf 어딘가에서 직선의 기울기는 -N(N-1)/2 일 것이다.

그런데 첫번째 a[i]/i를 지나고, 두번째 a[i]/i를 지나면서... 점점 기울기가 증가할 것이다.

+inf 어딘가에서 직선의 기울기는 N(N-1)/2로 변해있을 것이다.

기울기가 -x ~ x로 단조증가했기 때문에 극소값은 하나만 있다.

그래서 그냥 이진탐색 때리면 풀 수 있음.

(삼진탐색해도 당연히 됨!)

오버플로우 조심.

끗