[白俊]2285郵便局
白準2285郵便局
https://www.acmicpc.net/problem/2285
郵便局から各人までの距離の和は凸関数形式を呈する
->3点探索(ternary search)で凸関数の最小値を求める
なぜ放送するのか~!
https://www.acmicpc.net/problem/2285
郵便局から各人までの距離の和は凸関数形式を呈する
->3点探索(ternary search)で凸関数の最小値を求める
なぜ放送するのか~!
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long int ll;
int N;
vector<ll> X, A;
//우체국의 위치가 location일 때 각 사람들까지의 거리의 합
ll getDistSum(ll location) {
ll distSum = 0;
for (int i = 0; i < N; ++i)
distSum += (abs(location - X[i]) * A[i]);
return distSum;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N;
for (int i = 0; i < N; ++i) {
ll x, a;
cin >> x >> a;
X.push_back(x);
A.push_back(a);
}
//삼분 탐색 (X의 경계값도 답에 포함되도록 hi + 1, lo - 1)
double hi = 1000000000 + 1;
double lo = -1000000000 - 1;
for (int it = 0; it < 100; ++it) {
double mid1 = (2*lo + hi) / 3;
double mid2 = (lo + 2*hi) / 3;
if (getDistSum(mid1) > getDistSum(mid2))
lo = mid1;
else hi = mid2;
}
ll res = (lo + hi) / 2;
cout << res;
return 0;
}
Reference
この問題について([白俊]2285郵便局), 我々は、より多くの情報をここで見つけました https://velog.io/@sunjoo9912/백준-2285-우체국テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol