algorithm - 寻找有效的算法

    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;
}

最佳答案

对于某些序列，快速排序可能需要O（n^2）时间（通常已经排序的序列是错误的）。
我建议您尝试使用具有保证o（nlogn）性能的排序方法（例如heapsort或mergesort）。或者，您可能会发现，使用标准库中的排序例程将提供比您的版本更好的性能。

关于algorithm - 寻找有效的算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/27203387/