[BOJ] - 우체국

https://www.acmicpc.net/problem/2285

BOJ - 우체국

문제 유형: 그리디, 정렬

문제 난이도: Gold IV

시간 제한: 2초

메모리 제한: 128MB

 

문제

수직선과 같은 일직선상에 N개의 마을이 위치해 있다. i번째 마을은 X[i]에 위치해 있으며, A[i]명의 사람이 살고 있다.

이 마을들을 위해서 우체국을 하나 세우려고 하는데, 그 위치를 어느 곳으로 할지를 현재 고민 중이다. 고민 끝에 나라에서는 각 사람들까지의 거리의 합이 최소가 되는 위치에 우체국을 세우기로 결정하였다. 우체국을 세울 위치를 구하는 프로그램을 작성하시오.

각 마을까지의 거리의 합이 아니라, 각 사람까지의 거리의 합임에 유의한다.

 

입력

첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 X[1], A[1], X[2], A[2], …, X[N], A[N]이 주어진다. 범위는 |X[i]| ≤ 1,000,000,000, 0 ≤ A[i] ≤ 1,000,000,000 이며 모든 입력은 정수이다.

모든 A[i]를 합친 값은 0보다 크다.

 

출력

첫째 줄에 우체국의 위치를 출력한다. 단, 답이 여러 개일 경우 우체국의 위치가 작은 것을 출력한다.

 

풀이

가중치 중앙값 문제이다.

전체 사람 수를 구하고, 정렬을 해주고,

순차적으로 읽으면서 과반수를 넘기기 시작하게 한 값이 정답이 된다.

 

코드

C++

#include <bits/stdc++.h>

#include <ios>

using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

int main(int argc, char *argv[]) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<pll> parr(n);
    ll cnt = 0;
    for (int i = 0; i < n; i++) {
        cin >> parr[i].first >> parr[i].second;
        cnt += parr[i].second;
    }
    sort(parr.begin(), parr.end());
    ll pref_cnt = 0;
    for (int i = 0; i < n; i++) {
        pref_cnt += parr[i].second;
        if (pref_cnt * 2 >= cnt) {
            cout << parr[i].first << "\n";
            break;
        }
    }
    return 0;
}