2512번: 예산

📝 Memo

Memory : 2024

Time : 0

🖥️ Code

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

int arr[10001];
int main(){
    int n,m;
    scanf("%d",&n);
    int b,t=0;
    for(int i=0;i<n;i++){
        scanf("%d",&arr[i]);
        t = (arr[i]>t)?arr[i]:t;
    }
    scanf("%d",&m);
    b = m/n;
    int mid;
    int sum;
    while(b <= t){
        sum = 0;
        mid = (b+t)/2;
        for(int i=0;i<n;i++){
            if(arr[i] > mid)    sum += mid;
            else    sum += arr[i];
        }
        if(sum <= m) b = mid+1;
        else    t = mid-1;
    }
    sum = 0;
    for(int i=0;i<n;i++){
        if(arr[i] > mid)    sum += mid;
        else    sum += arr[i];
    }
    if(sum > m) mid -= 1;
    printf("%d",mid);
}