백준 28357 : 사탕 나눠주기

문제 설명

---

N명의 학생들의 점수와 사탕의 최대 개수 K가 주어졌을 때, 사탕의 총 개수가 K를 넘지 않도록 하면서 기준 점수 X를 가능한 한 낮게 설정하는 문제이다.

---

 

간단한 이분탐색 응용(파라미터 서치) 문제이다. 적절한 X를 이분탐색을 통해 찾으면 된다.

 

• X의 범위를 설정한다. X의 최솟값은 0, 최댓값은 10^12 이다.
• 이분 탐색을 통해 중간값 X를 선택한다.
• 선택된 X에 대해 각 학생에게 나누어 줄 사탕의 총 개수를 계산한다.
• 사탕의 총 개수가 K를 초과하지 않으면 high = mid - 1, 초과하면 low = mid + 1.
• 최종적으로 X의 최솟값을 찾는다.

---

소스 코드

#include <stdio.h>
#include <vector>
#include <algorithm>

int n;
long long k;
long long arr[500010];

long long satang(long long x)
{
    int i;
    long long res = 0;
    for(i=0;i<n;i++) {
        if(arr[i] > x) res += arr[i] - x;
    }
    return res;
}

int main()
{
    int i;
    scanf("%d %lld", &n, &k);
    for(i=0;i<n;i++) scanf("%lld", &arr[i]);
    long long low = 0, high = 1000000000000;
    while(low <= high) {
        long long mid = (low + high)/2;
        long long mid_res = satang(mid);
        if(mid_res <= k) high = mid - 1;
        else low = mid + 1;
    }
    printf("%lld", high + 1);
    return 0;
}