백준16564 히오스 프로게이머

작성일 | In

문제 링크

  • http://icpc.me/16564

문제 출처

  • 2018 Sogang Programming Contest (Master) D번

사용 알고리즘

  • Parametric Search

시간복잡도

  • O(N log 2e9)

풀이

입력 범위에 10억이 보이니 파라메트릭 서치를 고려해봅시다.
모든 캐릭터의 레벨을 m 이상으로 만들 수 있는지 판단하는 함수를 구현할 수 있다면 쉽게 풀 수 있을겁니다.

chk(m)이라는 함수를 모든 캐릭터의 레벨을 m 이상으로 만들 수 있을지 판단하는 decision함수로 정의합시다.
이 함수는 모든 캐릭터를 순회하면서 레벨이 m 이상이 되도록 레벨을 뿌려준 뒤, 뿌려준 레벨의 총합이 k를 넘는지 넘지 않는지 계산해주면 됩니다.

자세한 구현은 코드를 참고해주세요.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

vector<ll> v;
ll n, k;

bool chk(ll m){
	ll sum = 0;
	for(auto i : v){
		if(i < m) sum += (m - i);
	}
	return sum <= k;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> k; v.resize(n); for(int i=0; i<n; i++) cin >> v[i];

	ll l = 0, r = 2e9+2;
	while(l <= r){
		ll m = l + r >> 1;
		bool now = chk(m);
		bool nxt = chk(m+1);
		if(now && !nxt){
			cout << m; return 0;
		}
		if(now) l = m + 1;
		else r = m - 1;
	}
}