Educational round #75 D - Salary Changing ( 이분탐색 )

https://codeforces.com/contest/1251/problem/D

 

보자마자 이분탐색이나 dp겠구나 싶어서 이분탐색으로 접근했다. 하지만 시간이 부족해서 10분정도 오버해서 풀었다.

 

설명)

사람의 수 n과 가지고 있는 돈 s가 주어지고 n명의 사람에 대해 받을 수 있는 돈의 범위 [l,r]이 주어진다. 이 때 사람들에게 나누어주는 돈의 중간값의 최대를 구하는 문제이다.

 

l을 기준으로 사람들을 오름차순 정렬한다면 l, l, .... l, m, max(m,l), max(m, l) ... max(m,l) 인 경우가 최적이다. 

 

m값을 기준으로 오른쪽에 위치할 수 있는 사람은 r의 값이 m이상이어야 한다. 중간값 우측의 사람 수가 n/2미만이라면 그 값을 중간값으로 사용할 수 없다.

 

이 부분이 생각하기 좀 어려웠던 부분인데, 예를들어 s=26, arr에 (1,4), (10,11), (10,14)가 저장되어 있을 때 최대 중간값은 10이다. 이분탐색 시 이 값을 도출 하기 위해서 10이하의 값은 유효한 것으로 간주해야 한다는 의미다. 하지만 그 어떤 범위에도 속하지 않는 7(예를들어)은 사실 불가능한 중간값이다. 이런 값을 참이라고 넘기면 이분탐색의 특징에 따라서 결과적으론 유효한 최대값을 반환해 준다..

#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;

vector<P> arr;
ll n, s;

bool isPossible(ll m) {
	int cnt = 0;
	ll sum = 0;
	for (int i = n - 1; i >= 0; i--) {
		ll l = arr[i].first, r = arr[i].second;
		if (m<=r && cnt <= n/2) {
			cnt++;
			sum += max(l, m);
		}
		else
			sum += l;
	}
	if (cnt <= n / 2 || sum > s) return false;
	return true;
}

int main() {
	int t; cin >> t;
	while (t--) {
		cin >> n >> s;
		arr.resize(n);
		ll lo = 1e9, hi = 0;
		for (int i = 0; i < n; i++) {
			cin >> arr[i].first >> arr[i].second;
			lo = min(lo, arr[i].first);
			hi = max(hi, arr[i].second);
		}
		
		sort(arr.begin(), arr.end());

		while (lo < hi) {
			ll mid = (lo + hi+1) / 2;
			if (isPossible(mid)) lo = mid;
			else hi = mid-1;
		}

		cout << lo << '\n';
	}
}