5545번: 最高のピザ (Best Pizza)

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

$O(n\lg n)$

토핑의 열량이 큰 것부터 보며 올렸을 때 1달러 당 열량이 증가하는 것만 올리면 된다.

#include<cstdio>
#include<algorithm>
using namespace std;
int n, a, b, c, x[100];
int main() {
    scanf("%d%d%d%d", &n, &a, &b, &c);
    for (int i = 0; i < n; i++) scanf("%d", x + i);
    sort(x, x + n);
    for (int i = n; i--;) if (b*c < a*x[i]) c += x[i], a += b;
    printf("%d", c / a);
    return 0;
}