2285 우체국

2285 우체국 https://www.acmicpc.net/problem/2285

N개의 마을은 각각 $X_{i}$에 위치하고 $A_{i}$의 사람들이 살고 있다.
우체국을 하나 세울 때 각 사람들 까지의 거리가 최소가 되는 위치를 구하는 문제이다.

처음엔 삼진검색을 생각했으나 $O(N)$ 알고리즘이 떠올랐다.

이 문제에서 우체국은 N개의 마을 중 한 곳에 세워줘야 최적이다.
$a$와 $b$사이가 $d$인 두 마을만 있는 경우를 예시로 들어보겠다.

$a<=x<=b$인 $x$가 존재한다고 가정했을 때 우리가 구하고자하는 값은 $A(x-a) + B(b-x)$이다.

$(A-B)x-Aa+Bb$의 값을 최소화하는것이 우리의 목표인데 
$-Aa+Bb$는 상수이므로 $x$차수항만 생각해 본다면 
$A-B>0$인 경우에는 절대값을 낮춰야 하므로 $x=a$가 되어야하고
$A-B<0$인 경우에는 절대값을 키워야 하므로 $x=b$가 되어야 한다.
따라서 두 위치중 한 곳이 최적이다.
마을이 3개 이상인것도 확장시켜 생각해보면 증명이 가능하다.

현재 마을에 우체국을 세운다고 생각했을 때 마을 기준으로 오른쪽과 왼쪽에 있는 사람들의 수와 
거리를 잘 관리하면 해결할 수 있다.
__int128을 사용하여 통과하였다 ㅋㅋ;

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 1e5 + 5; int n; pair<ll, ll> arr[MAXN]; using Integer128 = __int128; std::ostream& operator<<(std::ostream& dest, const Integer128& value) {     Integer128 tmp = value < 0 ? -value : value;     std::array<char, 128> buffer;     auto d = buffer.begin();     while (tmp != 0) {         *d++ = "0123456789"[tmp % 10];         tmp /= 10;     }     if (value < 0) {         *d++ = '-';     }     std::ostream_iterator<char> out_it(dest);     std::reverse_copy(buffer.begin(), d, out_it);     return dest; } int main() {     cin >> n;     for (int i = 0; i < n; i++) cin >> arr[i].first >> arr[i].second;     sort(arr, arr + n);       __int128 fr = arr[0].second, en = 0;     __int128 dist = 0;     for (int i = 0; i < n; i++) {         if(i) en += (__int128)arr[i].second;         dist += (__int128)(arr[i].first - arr[0].first) * arr[i].second;     }     __int128 mx = dist;     __int128 ans = arr[0].first;     __int128 prv = 0;       for (int i = 1; i < n; i++) {         dist -= (__int128)(arr[i].first - arr[i - 1].first) * en;         dist += (__int128)(arr[i].first - arr[i - 1].first) * fr;         en -= (__int128)arr[i].second;         fr += (__int128)arr[i].second;         if (mx > dist) {             mx = dist;             ans = arr[i].first;         }         else if (mx == dist) {             if (ans > arr[i].first) ans = arr[i].first;         }     }     cout << ans;     return 0; } Colored by Color Scripter

cs

사실 더 간단한 풀이가 있다.
사람 수의 절반정도의 위치한 마을이 답이된다.

#include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; typedef long long ll; int n; pair<int, int> arr[MAXN]; int main() {     scanf("%d", &n);     ll sum = 0, s = 0;     for (int i = 0; i < n; i++) scanf("%d%d", &arr[i].first, &arr[i].second), sum += arr[i].second;     sort(arr, arr + n);     for (int i = 0; i < n; i++) {         s += arr[i].second;         if (s * 2ll >= sum) {             printf("%d\n", arr[i].first);             break;         }     }     return 0; } Colored by Color Scripter

cs