1246번: 온라인 판매

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


$O(m\lg m)$

당연하게도 pi가 큰 사람부터 팔아야 한다.
<pi>를 내림차순 정렬했을 때
답은 pi*i가 가장 클 때 pi, pi*i

#include<cstdio>
#include<algorithm>
#include<functional>
using namespace std;
int a[1001], n, m, r;
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++) scanf("%d", a + i);
    sort(a + 1, a + 1 + m, greater<int>());
    for (int i = 1; i <= m&&i <= n; i++) if (a[i] * i > a[r] * r) r = i;
    printf("%d %d", a[r], r*a[r]);
    return 0;
}