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을 사용하여 통과하였다 ㅋㅋ;
사실 더 간단한 풀이가 있다.
사람 수의 절반정도의 위치한 마을이 답이된다.
$-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;
}
| 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;
}
| cs |
