[1246번] 온라인 판매

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 정렬

이 문제는 결국 사람들에게 달걀을 팔았을 때 이윤을 최대로 해야하는 것이 관건인데

내림차순으로 정렬하면 arr[i]가 arr[i+1]보다 항상 크거나 같다.

따라서 arr[i] * i 가 최대 이윤이 될 것이고, 최대가 될때의 i와 그때의 arr[i] * i가 정답이 될 것이다. 

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <functional>
 
using namespace std;
 
int arr[1002];
 
int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
 
    for (int i = 1; i <= m; i++)
        scanf("%d", &arr[i]);
 
    sort(arr + 1, arr + 1 + m, greater<int>());
 
    int pos = 0;
    for (int i = 1; i <= m; i++)
    {
        if (i > n)
            break;
 
        if (arr[i] * i > arr[pos] * pos)
            pos = i;
    }
    printf("%d %d", arr[pos], arr[pos] * pos);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>