BOJ - 8986 - 전봇대

import sys

def func(arr, x):
    ret = 0
    for i in range(len(arr)):
        ret += abs(i * x - arr[i])

    return int(ret)

def solution():
    N = int(sys.stdin.readline())
    arr = list(map(int, sys.stdin.readline().split()))

    start = 1
    end = int(1e9)

    while(start + 3 <= end):
        left = (2 * start + end) // 3
        right = (start + 2 * end) // 3

        weightLeft = func(arr, left)
        weightRight = func(arr, right)

        if weightLeft < weightRight: end = int(right)
        else: start = int(left)


    ans = 1e18
    for i in range(start, end+1):
        ans = min(ans, func(arr, i))

    print(ans)

solution()

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