[백준 28357] 사탕 나눠주기 (C++)

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

문제

---

소수전공 수업을 마무리한 찬우는 축하의 의미로 학생들에게 사탕을 나누어 주려 한다. 구체적으로, 기준이 되는 음이 아닌 정수 X를 정한 뒤 최종 점수가 X점을 넘는 학생들에게 점수가 높은 만큼 많은 사탕을 줄 것이다. 즉, X+1점을 받은 학생은 1개, X+2점을 받은 학생은 2개, T(T>X)점을 받은 학생은 T−X개의 사탕을 받게 된다.

찬우는 학생들에게 최대한 많은 사탕을 나누어주고 싶기 때문에 기준 점수 X를 가능한 한 낮게 정하려 한다. 하지만, 지금 가지고 있는 돈으로는 사탕을 K개까지만 살 수 있기 때문에 사탕의 총 개수가 K개를 넘으면 안 된다.

찬우의 수업은 총 N명이 수강했고, i번째 학생은 Ai점을 받았다. 수강생의 수와 각 학생의 점수, 사탕의 최대 개수 K가 주어질 때 찬우를 위해 가능한 X의 최솟값을 구하는 프로그램을 작성해 주자.

 

입력

---

첫째 줄에 정수 N, K가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 5×10⁵; 0 ≤ K ≤ 10¹²)

둘째 줄에 N개의 정수 A1, A2, ⋯, AN이 공백으로 구분되어 주어진다. (0 ≤ Ai ≤ 10¹²)

 

출력

---

첫째 줄에 가능한 기준 X의 최솟값을 출력한다.

 

문제 풀이

---

이분탐색 문제.

 

주어진 값이 크므로 O(logn)에 탐색 가능한 이분 탐색 문제임을 유추할 수 있다. 이분 탐색의 mid를 기준점인 X로 잡는 매개변수 탐색을 진행하면 된다. 입력한 값들을 정렬한 후 left와 right로 mid를 정한 후, mid보다 큰 점수라면 해당 값에서 mid를 뺀다. 이 값들의 합이 M이 되는 mid의 최솟값을 구해주면 된다. 만약 준 사탕의 개수가 M보다 크다면 mid 값을 너무 작게 잡아 사탕을 너무 많이 나누어 준 것이다. 준 사탕의 개수가 M보다 작다면 기준점인 mid 값을 너무 크게 잡아 사탕을 너무 작게 준 것이다. 물론 나누어주는데에는 문제 없으므로 mid값을 저장하며 최솟값을 갱신시켜주면 된다.

 

아래는 코드.

#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;
long long* arr;
long long N, M;
long long answer;

void binarySearch(long long start, long long end)
{
	long long left = start;
	long long right = end;
	while (left <= right)
	{
		long long standard = (left + right) / 2;
		long long candySum = 0;
		for (int i = 0; i < N; i++)
		{
			if (arr[i] < standard)
			{
				continue;
			}
			else
			{
				candySum += arr[i] - standard;
			}
		}
		if (candySum <= M)
		{
			answer = min(answer, standard);
			right = standard - 1;
		}
		else
		{
			left = standard + 1;
		}
	}
}

int main()
{	
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	answer = LLONG_MAX;
	cin >> N >> M;
	arr = new long long[N];
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
	sort(arr, arr + N);
	binarySearch(0, 1000000000001);
	cout << answer << "\n";
	return 0;
}