[백준] 8986 전봇대

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
 
#define INF 1e18;
using ll = long long;
 
int N, pole[1000000];
 
ll f(ll x)
{
    ll result = 0;
    for (int i = 1; i < N; ++i)        result += abs(x*i - pole[i]);
    return result;
}
 
int main() {
    
    scanf("%d", &N);
    for (int i = 0; i < N; ++i)        scanf("%d", &pole[i]);
 
    int low = 0, high = INF;
    while (high - low >= 3) 
    {
        ll a = (low * 2 + high) / 3;
        ll b = (low + high * 2) / 3;
        if (f(a) <= f(b)) high = b;
        else low = a;
    }
 
    ll result = INF;
    for (int i = low; i <= high; ++i)        result = min(f(i), result);
 
    printf("%lld\n", result);
}