2512번: 예산

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


$O(n\lg n)$

n개의 수를 정렬한 다음, 각 인접한 수 사이마다 예산 상한의 최대값이 되는지 확인한다.

#include<cstdio>
#include<algorithm>
int n, t, m, i, a[10000];
int main() {
    scanf("%d", &n);
    for (i = 0; i < n; i++) scanf("%d", a + i);
    std::sort(a, a + n);
    scanf("%d", &m);
    for (i = 0; t + a[i] * (n - i) < m&&i < n; i++) t += a[i];
    printf("%d", i == n ? a[n - 1] : (m - t) / (n - i));
    return 0;
}