본문 바로가기

알고리즘 관련/BOJ

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를 이용하여 문제를 해결 할 수 있다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#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;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)14288 내리 갈굼4  (1) 2018.07.07
BOJ)15745 Snow Boots  (0) 2018.07.03
BOJ)13274 수열  (0) 2018.07.02
BOJ)15589 Lifeguards (Silver)  (0) 2018.06.26
BOJ)14965 Lozinke  (0) 2018.06.26