Смартфон Codechef проблема логики путаницы

Question

Вы разрабатываете приложение для смартфона. У вас есть список потенциальных клиентов для вашего приложения. У каждого клиента есть бюджет, и он будет покупать приложение по заявленной вами цене тогда и только тогда, когда цена будет меньше или равна его бюджету.

Вы хотите установить цену так, чтобы доход, полученный вами отприложение развернуто. Найдите этот максимально возможный доход.

Например, предположим, что у вас есть 4 потенциальных клиента, и их бюджеты составляют 30, 20, 53 и 14. В этом случае максимальный доход, который вы можете получить, составляет 60.

мой друг сказал мне, что просто отсортируй массив и попробуй использовать

ar [i] * (ni), хотя я реализовал, я не понял всю логику. Очень нужна помощь с объяснением

#include<bits/stdc++.h>
using namespace std;

int maximumProfit(int budget[], int n) {

    int ans=INT_MIN;
    sort(budget,budget+n);
    for(int i=0;i<n;i++)
    {
        ans=max(ans,budget[i]*(n-i));
    }
    return ans;
}

Answer 1

Интуиция. Скажем, самый бедный человек в оптимальном решении имеет бюджет х. Тогда вы всегда можете выбрать x в качестве цены, потому что все остальные, по крайней мере, настолько же богаты, и выбор более низкой цены только уменьшит ваш доход (если только он не самый бедный). Осознав это, вы просто перебираете клиентов, чтобы найти человека, который является самым бедным в оптимальном решении (их может быть несколько, но затем вы выбираете все из них). Общий доход - это бюджет кандидата, умноженный на количество людей, которые, по крайней мере, столь же богаты, и составляет budget[i] * (n - i), поскольку бюджеты отсортированы в неубывающем порядке.