[ BOJ / C++ ] 16564번 히오스 프로게이머

이번 문제는 이분탐색을 통해 해결하였다.

• 우선 범위가 최대 10억이므로 자료형은 long long을 사용한다.
• 입력받은 x중 가장 작은 수를 사용해야 하므로 오름차순으로 sort해준다.
• 이분탐색의 범위는 가장 작은 수인 x[0]과 x[0]이 될 수 있는 수 중 가장 큰 수인 x[0]+k로 잡는다.
• mid를 최소값으로 하기 위한 과정에서 필요한 수를 cnt변수에 담는다. 이때 k를 넘어가도 상관없다.
• cnt가 k보다 크다면 결과값이 현재 mid보다 작아야 하므로 back에 mid-1을 넣어준다.
• cnt가 k보다 작거나 같다면 front에 mid+1을 넣어준다.

#include <iostream>
#include <algorithm>
#define MAX 1000001
using namespace std;

int n;
long long k;
long long x[MAX];
long long cnt=0;
long long result=0;

void Input(){
    cin>>n>>k;
    for(int i=0; i<n; i++){
        cin>>x[i];
    }
    sort(x, x+n);
}

void BinarySearch(){
    long long front = x[0];
    long long back = x[0]+k;
    while(front<=back){
        long long mid = (front+back)/2;
        cnt=0;
        for(int i=0; i<n; i++){
            if(mid>x[i]){
                cnt+=(mid-x[i]);
            }
            else break;
        }
        if(cnt>k){
            back=mid-1;
        }
        else{
            result=mid;
            front=mid+1;
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Input();
    BinarySearch();
    cout<<result<<endl;
    return 0;
}