# [Gold IV] 우체국 [문제 링크](https://www.acmicpc.net/problem/2141) ## 문제 설명 <p>수직선과 같은 일직선상에 N개의 마을이 위치해 있다. i번째 마을은 X[i]에 위치해 있으며, A[i]명의 사람이 살고 있다.</p> <p>이 마을들을 위해서 우체국을 하나 세우려고 하는데, 그 위치를 어느 곳으로 할지를 현재 고민 중이다. 고민 끝에 나라에서는 각 사람들까지의 거리의 합이 최소가 되는 위치에 우체국을 세우기로 결정하였다. 우체국을 세울 위치를 구하는 프로그램을 작성하시오.</p> <p>각 마을까지의 거리의 합이 아니라, 각 사람까지의 거리의 합임에 유의한다</p> ## 입력 <p>첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 X[1], A[1], X[2], A[2], …, X[N], A[N]이 주어진다. 범위는 |X[i]| ≤ 1,000,000,000, 1 ≤ A[i] ≤ 1,000,000,000 이며 모든 입력은 정수이다.</p> ## 출력 <p>첫째 줄에 우체국의 위치를 출력한다. 가능한 경우가 여러 가지인 경우에는 더 작은 위치를 출력하도록 한다.</p> ## 풀이 모든 사람들 중 중간에 위치한 사람이 위치한 집이 최선의 경우입니다. 만약 짝수 명이고 두 집 사이에 끼어 있는 경우 그 사이가 전부 최소여서 가장 작은 왼쪽 집을 출력하면 됩니다. ``` c++ #include<bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; long long sum=0; vector<pair<int, int>> v(n); for(int i=0;i<n;i++) { cin >> v[i].first >> v[i].second; sum += v[i].second; } sort(v.begin(), v.end()); long long cur=0; for(auto [x, a]:v) { cur += a; if(cur>=(sum+1)/2) { cout << x; return 0; } } } ```