algorithm - 寻找有效的算法

Question

    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.
**Input format**
Line 1 : N, the total number of potential customers.
Lines 2 to N+1: Each line has the budget of a potential customer.
**Output format**
The output consists of a single integer, the maximum possible revenue you
can earn from selling your app.

  Also, upper bound on N is 5*(10^5) and upper bound on each customer's budget is 10^8.

这是我要解决的问题。我的策略是对预算列表进行排序，然后将每个预算与其在序列中的位置索引相乘——然后打印结果序列的最大值。然而，这似乎非常耗时(至少在我实现它的方式上 - 我附上了代码以供引用)。我的时间上限是 2 秒。谁能帮我找一个 更省时的算法(或者可能是实现我的算法的更有效方法)？

这是我的解决方案:

#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>

using namespace std;

long long max(long long[],long long);
void quickSortIterative(long long[],long long,long long);
long long partition(long long[],long long,long long);
void swap(long long*,long long*);

int main(){
    long long n,k=1;
    scanf("%lld",&n);
    if(n<1 || n > 5*((long long)pow(10,5))){
        exit(0);
    }
    long long budget[n],aux[n];
    for(long long i=0;i<n;i++){
        scanf("%lld",&budget[i]);
        if(budget[i]<1 || budget[i] > (long long)pow(10,8)){
             exit(0);
        }
    }
    quickSortIterative(budget,0,n-1);
    for(long long j=n-1;j>=0;j--){
        aux[j] = budget[j]*k;
        k++;
    }
    cout<<max(aux,n);
    return 0;
}

long long partition (long long arr[], long long l, long long h){
    long long x = arr[h];
    long long i = (l - 1);

    for (long long j = l; j <= h- 1; j++)
    {
        if (arr[j] <= x)
        {
            i++;
            swap (&arr[i], &arr[j]);
        }
    }
    swap (&arr[i + 1], &arr[h]);
    return (i + 1);
}

void swap ( long long* a, long long* b ){
    long long t = *a;
    *a = *b;
    *b = t;
}

void quickSortIterative(long long arr[], long long l, long long h){
    long long stack[ h - l + 1 ];
    long long top = -1;
    stack[ ++top ] = l;
    stack[ ++top ] = h;
    while ( top >= 0 ){

        h = stack[ top-- ];
        l = stack[ top-- ];
        long long p = partition( arr, l, h );
        if ( p-1 > l ){
            stack[ ++top ] = l;
            stack[ ++top ] = p - 1;
        }
        if ( p+1 < h ){
            stack[ ++top ] = p + 1;
            stack[ ++top ] = h;
        }
    }
} 

long long max(long long arr[],long long length){
    long long max = arr[0];
    for(long long i=1;i<length;i++){
        if(arr[i]>max){
            max=arr[i];
        }
    }
    return max;
}

Answer 1

对于某些序列，快速排序可能需要 O(n^2) 时间(通常已经排序的序列是错误的)。

我建议您尝试使用具有保证 O(nlogn) 性能的排序方法(例如堆排序或合并排序)。或者，您可能会发现使用标准库中的排序例程会提供比您的版本更好的性能。