[Codeforces 1084B] Kvass and the Fair Nut

[Codeforces 1084B] Kvass and the Fair Nut

N개의 음료수의 용량(v_i)과 s가 주어진다. 각각의 음료수에서는 최소 0부터 최대 (v_i)까지 음료수를 빼낼 수 있다. 이렇게 음료는 빼내서 s가 되도록 만들어야 한다. 이때 가장 적게 든 음료수의 용량이 최대가 되도록 하는 문제이다.

처음 딱 봤을 때는 당연히 바이너리 서치로 푸는 문제 인 줄 알았다.

#include<stdio.h>
#include<algorithm>
using namespace std;
typedef long long ll;
int fMax(ll a,ll b){
    return a>b?a:b;
}
int main(){
    ll n,s;    scanf("%lld %lld",&n,&s);
    ll arr[1009];
 
    ll sum=0;
    int l=0,r=0;
 
    for(int i=0 ; i<n ; i++){
        scanf("%lld",&arr[i]);
        sum+=arr[i];
        r=fMax(r,arr[i]);
    }
 
    if(sum<s){
        printf("-1\n");
        return 0;
    }
    ll ans;
 
    //upper bound
    while(r > l+1){
        int mid=(l+r)/2;
        ll cur_sum=0;
        bool check=false;
        
        for(int i=0 ; i<n ; i++){
            int diff=arr[i]-mid;
            if(diff<0){
                check=true;
                break;
            }
            cur_sum+=diff;
        }
 
        if(cur_sum<s || check){
            r=mid;
        }
        else{
            l=mid;
        }
    }
    printf("%d\n",l);
    return 0;
}

그런데 사실 그리디로도 풀 수 있어서 O(N)만에 가능하다(바이너리 서치는 O(N*logN)). N=1000으로 작았기에 망정이지, 1000만 정도 됐으면 아마 못 풀었을 거다.

그리디 풀이에서의 핵심은 문제의 답은 항상 입력으로 주어진 v 중에서 가장 작은 v값보다 작거나 같다는 것이다. 음료수를 채우는 행위는 불가능하기 때문이다. 그래서 우선 모든 음료수의 용량에서 가장 작은 음료수의 용량(=min_cap이라고 하자)을 빼면서 동시에 그 차를 diff 변수에 저장한다. 이 시행을 하고나면 모든 음료수의 용량은 min_cap과 동일해진다. 그리고 diff의 값이 s보다 크다면 정답은 바로 min_cap이 된다. 만약 여전히 s가 더 크다면 남은 음료수의 양이라는 의미에 remain변수를 만들고 이 값은 (s-diff)와 같다. 그리고 remain을 n으로 나눈 몫을 min_cap에서 빼준다. 이 시행은 남아있는 음료수 양에 대해서 모든 음료수가 공평하게 나눠준다는 뜻이다. 그래야만 남아있는 최소 용량이 최대가 되도록 할 수 있다. 그리고 reamin에서 n으로 나누어 떨어지지 않는다면 추가로 1을 더 빼주면 된다.

#include<stdio.h>
#include<algorithm>
using namespace std;
typedef long long ll;
int arr[1009];
int main(){
    ll n,s;    scanf("%lld %lld",&n,&s);
 
    ll sum=0;
    int min_cap=1<<30;
    for(int i=0 ; i<n ; i++){
        scanf("%d",&arr[i]);
        sum+=arr[i];
        min_cap=min(min_cap,arr[i]);
    }
 
    if(sum<s){
        printf("-1\n");
        return 0;
    }
 
    ll diff=0,ans=0;
    for(int i=0 ; i<n ; i++){
        diff+=(arr[i]-min_cap);
    }
    ans=min_cap;
    if(diff<s){
        ll remain=s-diff;
        ans-=(remain/n);
        if(remain%n) ans--;
    }
    printf("%lld\n",ans);
    return 0;
}