BOJ)14400 편의점2

문제: icpc.me/14400    

고객들의 좌표가 주어 질 때 고객들과의 맨하탄 거리의 합의 최솟값을 구하는 문제이다.

문제를 함수로 표현하면 |x-a1|+|y-b1|+|x-a2|+|y-b2|+|x-a3|+|y-b3|+..... 꼴의 최솟값을 구하는 문제가 되는데,

여기서 x의 절댓값 함수들과 y의 절댓값 함수들을 독립 시켜서 보면 |x-a1|+|x-a2|+...|x-an|의 그래프는 한개의 극값(최솟값)을 가지는 unimodal 함수가 됨을 알 수 있다.

따라서 ternary search를 이용하여 문제를 해결 할 수 있다.

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
vector<ll> x,y;
ll n;
ll f(ll c,vector<ll> &par){
    ll ret=0;
    for(auto next:par)
        ret+=abs(next-c);
    return ret;
}
ll ternary_search(vector<ll> &par){
    ll ret=1e18;
    ll lo=-1000010,hi=1000020;
    while(lo+3<hi){
        int l=(2*lo+hi)/3,r=(lo+2*hi)/3;
        if(f(l,par)>f(r,par))lo=l;
        else hi=r;
    }
    for(int i=lo;i<=hi;i++)
        ret=min(ret,f(i,par));
    return ret;
}
int main(){
    scanf("%lld",&n);
    for(int i=0;i<n;i++){
        ll xx,yy;
        scanf("%lld%lld",&xx,&yy);
        x.push_back(xx);
        y.push_back(yy);
    }
    printf("%lld\n",ternary_search(x)+ternary_search(y));
    return 0;
}