Boj 8986) 전봇대

문제

백준 8986

설명

각 전봇대마다 필요한 거리의 함수는 Unimodal 하다. Unimodal 한 함수의 합 역시 Unimodal 한 함수이므로 볼록함수의 극값을 구하는 기법인 삼분탐색을 수행하면 값을 구할 수 있다.

원리는 간단한데, 막상 처음 보니 저걸 떠올리기가 너무 어려웠다.

시간 복잡도

O(\(\mathrm{N}\log{\mathrm{N}}\))

코드

using ll = long long;
ll arr[100001], n;

ll Calc(ll d)
{
    ll res = 0;
    for (ll i = 1; i < n; i++) res += abs(arr[i] - d * i);
    return res;
}

int main()
{
    fastio;

    cin >> n;
    for (int i = 0; i < n; i++) cin >> arr[i];

    ll s = 0, e = 1e9;
    while (e - s > 2)
    {
        ll d = (e - s) / 3;
        ll p = s + d, q = s + (d << 1);
        ll pv = Calc(p), qv = Calc(q);
        pv > qv ? s = p+1 : e = q-1;
    }
    ll ans = 1e18; // 최댓값 주의. 1e9 같은 걸론 부족함.
    for (int i = s; i <= e; i++)
        ans = min(ans, Calc(i));
    cout << ans;
}