[백준 28357] 사탕 나눠주기

오랜만에 이분탐색 문제를 풀자

 

푸는데 초반에 시작 최소값을 그냥 주어진 값들 중  최소값으로 넣었는데

답이 0일 수도 있다는 것을 깨닫고 이거로 바꿈

cout << binary_search(0, v.back());

 

답이 음이 아닌 정수가 된다 했으므로 0도 답이 될 수 있다.

가령 이런 경우

 

2 3 

1 2

 

이런 경우는 0이 답인데 초기 최솟값을 값들 중 최소값으로 주면 답이 1이 나온다

 

그 다음 주의해야할 것은 

// 정답일 수 있는 경우들
// 남으면 왼쪽으로
if (getsum(mid) <= K) {
	max = mid - 1;
	ans = mid;
}

 

항상 답이 될 수 있는 경우는 저장하고 넘어가야한다는 거

 

답 가능 -> 답 불가능 -> 근데 while(min <= max) 안만족해서 끝남

 

이런 경우에는 답을 mid로 내면 틀린다.

mid가 답이 불가능한 경우에 최신화 되기 때문이다.

 

그래서 답이 가능한 경우에는 항상 "답"을 최신화해줘야함

 

아 그리고 입력값때문에 모두  long long으로 제출직전에 다 바꿔줬다.

 

---

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<long long> v;
long long N, K;

long long getsum(long long mid) {
	long long sum = 0;

	for (int i = 0; i < N; i++) {
		if (v[i] > mid) {
			sum += v[i] - mid;
		}
	}

	return sum;
}

long long binary_search(long long min,long long max) {

	long long ans = 0;

	while (min<=max) {
		long long mid = (min + max) / 2;

		// 정답일 수 있는 경우들
		// 남으면 왼쪽으로
		if (getsum(mid) <= K) {
			max = mid - 1;
			ans = mid;
		}
		else {
			min = mid + 1;
		}
	}
	return ans;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	long long x;
	cin >> N >> K;

	for (int i = 0; i < N; i++) {
		cin >> x;
		v.push_back(x);
	}

	sort(v.begin(), v.end());

	cout << binary_search(0, v.back());
	
	return 0;
}