[BOJ 8986] 전봇대

문제는 여기에서 확인할 수 있다.

---

전봇대의 좌표를 $p$의 배수로 통일 시킬 때, 전봇대를 이동시키는 비용은 아래와 같다.

$$f\left(p\right) = \sum \left\vert x_i - pi \right\vert$$

 

따라서, $f\left(p\right)$를 최소화 시키면 되고, 이는 삼분탐색으로 가능하다.

#include<bits/stdc++.h>
 
using namespace std;
 
#define ioinit() ios::sync_with_stdio(false); cin.tie(nullptr);
#define INF INT_MAX
#define LINF LONG_MAX
#define x first
#define y second
#define MOD 1000000007
 
typedef long long lld;
typedef pair<int, int> pii;
 
int N, A[100005];
 
lld f(lld x) {
    lld ret = 0;
    for (int i = 0; i < N; i++) {
        ret += abs(i * x - A[i]);
    }
    return ret;
}
 
int main() {
    ioinit();
    cin >> N;
    for (int i = 0; i < N; i++) cin >> A[i];
    lld s = 1, e = 1000000000;
    while (e - s > 10) {
        lld a = (s * 2 + e) / 3;
        lld b = (s + e * 2) / 3;
        lld p = f(a);
        lld q = f(b);
        if (p == q) {
            s = a;
            e = b;
        } 
        else if (p > q)
            s = a;
        else
            e = b;
    }
    lld rst = LINF;
    for (int i = s; i <= e; i++)
        rst = min(rst, f(i));
    cout << rst;
    return 0;
}