[백준]우체국(2285)

문제 링크 : [백준]우체국(2285)

2285번: 우체국

 

문제 설명

N개의 마을이 있고, 각 마을은 Xi에 위치하고, Ai명의 사람이 산다고 합니다.

이 때, 특정 위치에 우체국을 세웠을 때, 모든 사람과 우체국간의 거리가 최소가 되는 우체국의 위치를 구하세요.

입력

N(마을의 갯수, 1 <= N <= 100,000)

Xi(마을의 위치, -1,000,000,000 <= Xi <= 1,000,000,000)

Ai(마을에 사는 사람의 수, , -1,000,000,000 <= Ai <= 1,000,000,000)

3
1 3
2 5
3 3

 

출력

2

 

카테고리

#삼분탐색

 

시간 복잡도 상한

O(NlogM)(M은 우체국을 놓을 수 있는 위치의 범위)

 

해결 방법

1. f(x)를 우체국 위치가 x일 때, 모든 사람들까지의 거리라고 정의하면, f(x)는 O(N)에 구할 수 있습니다.
2. 그리고 f(x)는 이차함수 그래프를 가지기 때문에 삼분 탐색으로 구할 수 있습니다.

시간복잡도

O(NlogM)(M은 우체국을 놓을 수 있는 위치의 범위)

코드

#include<iostream>
#include<algorithm>
#define N 100000
using namespace std;
typedef long long L;
int n,i,l=-1e9,r=1e9,m;
L x,y,a[N],b[N],q;
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    for(;i<n;i++)cin>>a[i]>>b[i];
    while(l<=r){
        m=(l+r)/2;
        for(x=y=i=0;i<n;i++){
            x+=abs(a[i]-m)*b[i];
            y+=abs(a[i]-(m+1))*b[i];
        }
        if(x<=y)r=m-1;
        else l=m+1;
    }
    cout<<l;
}