전봇대 (8986번)

#include<iostream>
using namespace std;

const long long INF = (~(unsigned long long)0 >> 1);
const int MAX_N = 100000;
int N;
long long Ary[MAX_N];

long long Diff(long long Dist) 
{
    long long Ret = 0;
    for (int i = 1; i < N; ++i)
        Ret += abs(Ary[i] - Dist * i);
    return Ret;
}

long long MinDiff() 
{
    long long lo = 1, hi = 1e9;
    while (lo + 3 < hi) 
    {
        long long aab = (lo * 2 + hi) / 3;
        long long abb = (lo + hi * 2) / 3;
        if (Diff(aab) < Diff(abb))
            hi = abb;
        else
            lo = aab;
    }
    
    long long ans = INF;
    for (long long i = lo; i <= hi; ++i)ans = min(ans, Diff(i));
    return ans;
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(0);

    cin >> N;

    for (int i = 0; i < N; i++)
        cin >> Ary[i];

    cout << MinDiff();

    return 0;
}