백준 2141 우체국 C++

 

간단한 해설

 

N이 최대 10^5,  | X[i] |와 A[i] 모두 최대 10^9 이므로 long long형이더라도 overflow가 될 수 있는 가능성을 생각만 해뒀다.

 

우리가 구하고자 하는 값은 한 지점을 정하고, 그 지점에서  각 사람까지의 거리의 합, 그 합이 최솟값이 되는 지점을 구하고 싶은 것이다.

 

대충 식으로 표현하면 다음과 같다.

 

 

한 지점을 x로 두고, 그 지점에서 각 사람까지의 거리의 합이 f(x)이다.

 

우리가 고등학교 수학에서 배웠듯이 이 f(x)의 값이 최소가 되는 지점은 무조건 X의 원소인 X[i]이다.

 

여기서 미분으로 경향성을 찾아도 되고 여러 가지 방법이 있지만, 제일 편한 방법은 그냥 1차 함수이니까 계수만 보면 된다.

 

A[i]가 절반이 넘어가는 그 순간의 X[i]가 답이다.

 

 

답

 

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;
int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	int n;
	cin>>n;
	vector<pair<ll,ll>> v(n);
    ll p=0;
	for(int i=0;i<n;++i){
		cin>>v[i].first>>v[i].second;
        p+=v[i].second;
	}
	sort(v.begin(),v.end());
    ll gae=0;
    for(int i=0;i<n;++i){
        gae+=v[i].second;
        if(gae*2>=p){
            cout<<v[i].first;
            break;
        }
    }
}