우체국 C++ - 백준 2141

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

그리디 문제.

백준 안테나 문제와 유사한 문제.

문제 접근

안테나 문제와 마찬가지로 우측 좌측의 사람의 수 차이 만큼 거리가

감소 혹은 증가 하기 때문에 우측, 좌측 사람 수 차이가

양수에서 음수로 바뀌는 부분이 답이다.

이때 답의 후보는 두개로 나뉘는데 두개 중 우측 좌측사람 수 차이가

더 작은 값이 결국 답이기 때문에 마지막에 골라서 출력해준다.

코드는 다음과 같다.

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n,X,A; cin >> n;
	vector<pair<int, int>> v;
	vector<pair<ll, ll>> d;
	for(int i=0;i<n;i++){cin >> X >> A; v.push_back({X,A});}
	sort(v.begin(),v.end(),[](pair<int, int> l, pair<int, int> r)->bool{return l.first<r.first;});
	d.push_back({0,0});
	for(int i=1;i<n;i++) d.push_back({d[i-1].first+v[i-1].second,0});
	for(int i=1;i<n;i++) d[n-(i+1)].second=d[n-i].second+v[n-i].second;
	int l=0;
	int r=n-1;
	while(d[l].second>d[l].first) l++;
	while(d[r].first>d[r].second) r--;
	ll dl=d[l].first-d[l].second;
	ll dr=d[r].second-d[r].first;
	if(dl<dr) cout << v[l].first;
	else cout << v[r].first;
	return 0;
}