[BOJ 28357] 사탕 나눠주기

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

28357번: 사탕 나눠주기

 

- 문제 요약

 

소수전공 수업을 마무리한 찬우는 축하의 의미로 학생들에게 사탕을 나누어 주려 한다.

구체적으로, 기준이 되는 음이 아닌 정수 X를 정한 뒤 최종 점수가 X점을 넘는 학생들에게 점수가 높은 만큼 많은 사탕을 줄 것이다.

즉, X+1점을 받은 학생은 1개, X+2점을 받은 학생은 2개, T(T > X)점을 받은 학생은 T - X개의 사탕을 받게 된다.

찬우는 학생들에게 최대한 많은 사탕을 나누어주고 싶기 때문에 기준 점수 X를 가능한 한 낮게 정하려 한다.

하지만, 지금 가지고 있는 돈으로는 사탕을 K개까지만 살 수 있기 때문에 사탕의 총 개수가 K개를 넘으면 안 된다.

찬우의 수업은 총 N명이 수강했고, i번째 학생은 Ai점을 받았다.

수강생의 수와 각 학생의 점수, 사탕의 최대 개수 K가 주어질 때 찬우를 위해 가능한 X의 최솟값을 구하는 프로그램을 작성해 주자.

 

 

- 알고리즘 정리

 

X가 증가할수록 필요한 사탕의 개수는 줄어들거나 동일합니다.

그러므로 이분 탐색을 돌리며 가장 작은 X를 찾아주면 됩니다.

 

 

- 코드 작성

 

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

#define MAX 500001
typedef long long ll;
ll n,k,arr[MAX],l,r=1e12;

bool f(ll x){
	ll result=0;
	for(int i=1;i<=n;i++){
		result+=max(0LL,arr[i]-x);
	}
	return result<=k;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>arr[i];
	}
	while(l<r){
		ll mid=(l+r)/2;
		if(f(mid)){
			r=mid;
		}
		else{
			l=mid+1;
		}
	}
	cout<<r;
}

코드 제출 결과