You are developing a smartphone app. You have a list of potential customers for your app. Each customer has a budget and will buy the app at your declared price if and only if the price is less than or equal to the customer's budget.
You want to fix a price so that the revenue you earn from the app is maximized. Find this maximum possible revenue.
For instance, suppose you have 4 potential customers and their budgets are 30, 20, 53 and 14. In this case, the maximum revenue you can get is 60.
my friend told me that just sort the array and try using
ar[i]*(n-i) although i implemented i didnt under stood the whole logic.really need help with the explanation
#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;
}
Intuition: Let's say that the poorest person in the optimal solution has a budget of x. Then you can always choose x as the price because everyone else is at least as rich and choosing a lower price will only reduce your revenue (unless he is not the poorest). After realizing this, you're simply iterating over the customers to find the person who is the poorest in the optimal solution (there can be multiple but then you choose all of them). The total revenue is the budget of the candidate times the number of people who are at least as rich, which is budget[i] * (n - i) since the budgets are sorted in non-decreasing order.