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

예산을 크기 순으로 정렬하고 나면 모든 요청이 배정될 수 없는 순간이 언제인지를 알 수 있습니다. D[i] = budget[0] + budget[1] + ... + budget[i-1] 이라고 하면 D[i]는 O(N)으로 채울 수 있습니다.

이 때 D[i] + (N-i) * budget[i-1] > M이 되는 최초의 지점 i를 찾게 되면 budget[0]~budget[i-1]는 정상적으로 집행하고 이후로는 (M-D[i-1]) / (N-i+1)원씩 배정하면 됩니다.

https://github.com/encrypted-def/BOJ/blob/master/2512.cpp