백준 2141번 우체국 c++ 풀이

문제

수직선과 같은 일직선상에 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, 1 ≤ A[i] ≤ 1,000,000,000 이며 모든 입력은 정수이다.

출력

첫째 줄에 우체국의 위치를 출력한다. 가능한 경우가 여러 가지인 경우에는 더 작은 위치를 출력하도록 한다.

예제 입력 1 복사

3
1 3
2 5
3 3

예제 출력 1 복사

2

 

 

누적합과 이분탐색을 통해서 풀 수 있는 문제, 답안을 참고하였다.

 

현재까지의 누적합이 우체국 기준 오른쪽의 누적합들 보다 더 크다면 왼쪽으로 탐색, 더 작다면 오른쪽으로 탐색

 

- c++ 풀이

#include <bits/stdc++.h>

#define ll long long int

using namespace std;
ll sum[100001];


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    ll N;
    cin >> N;
    vector<pair<ll, ll>> v;
    for (int i = 0; i < N; i++) {
        ll a, b;
        cin >> a >> b;
        v.push_back({a, b});
    }
    sort(v.begin(), v.end());
    sum[0] = v[0].second;

    for (int i = 1; i < N; i++) {
        sum[i] = sum[i - 1] + v[i].second;
    }

    ll start = 0;
    ll end = v.size() - 1;
    ll idx = 987654321;

    while (start <= end) {

        ll mid = (start + end) / 2;


        if (sum[mid] >= sum[N - 1] - sum[mid]) {
            idx = min(idx, v[mid].first);
            end = mid - 1;
        } else {
            start = mid + 1;
        }


    }

    cout << idx << "\n";

    return 0;
}