将 O(n^2) 的复杂性降低到至少 O(n log n)

Question

我想降低这个程序的复杂性，但我不知道该怎么做。

Program:
You are holding an event and you need money. Every person that participates will give percentage of their salary to the event, but every person must give the same percentage. If the percentage you chose is for example 30% and person P is only willing to give 20%, then person P wont give anything. If you chose 30% and person P is willing to give 80%, then person P will only give 30%.

You want to figure out what is the percentage that will get you the most money.

Inputs are:

First line: Number of people that participate (n)
Next n lines: Salary of i-th person, Max percentage of salary that i-th person is willing to give away

Output:
First line: Largest amount of money that you can get for the event.

Example:

Input:
4
100001 83.2
40001 20
90001 77.32
300001 1.88
Output:
146909.5464
Program chose that the percentage that will bring the most money is 77.32 and wrote that the money you can get from that percentage is (100001+90001)*77.32

#include <iostream>
#include <iomanip>

using namespace std;

int N,A[200000];
double P[200000],suma,maxsuma;

int main(){

ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

cin>>N;
for(int i=0;i<N;i++){
    cin>>A[i]>>P[i];
}
for(int i=0;i<N;i++){
    suma=0;
    for(int j=0;j<N;j++){
        if(P[j]>=P[i]){
            suma+=P[i]*A[j]/100.0;
        }
    }
    maxsuma=max(suma,maxsuma);
}

cout<<fixed<<setprecision(20)<<maxsuma;

}

Answer 1

首先，按照他们愿意给予的百分比降序对所有人员进行排序。现在无论你选择什么百分比，只有名单上的一些第一批人会真正付钱。因此，你会赚取最多的利润，这是最后一个人的百分比。现在还要注意，从这个前缀开始，每个人都给了 salary * percentage，所以总付款是 total salary * percentage。如果 s[i] 是所有人到第 i 个指数的总工资，那么 s[i] = s[i - 1] + a[i] 其中 a[i] 是第 i 个人的工资。因此，您只需编写一个循环，首先使用上一次迭代中已知的 s[i - 1] 计算 s[i]，然后将其乘以第 i 个人的百分比；在所有这些值中选择最高的一个。

我修改了你的代码以使用这个想法。

#include <iostream>
#include <iomanip>
#include <algorithm>

using namespace std;

int N;
std::pair<int, int> A[200000]
double maxsuma;

int main(){

ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

cin>>N;
for(int i=0;i<N;i++){
    cin>>A[i].second>>A[i].first;
}
std::sort(A, A + N, std::greater<std::pair<int, int>>());
int suma = 0;
for(int i=0;i<N;i++){
    suma += A[i].second;
    maxsuma=max(suma * A[i].first / 100.0, maxsuma);
}

cout<<fixed<<setprecision(20)<<maxsuma;

}

将 O(n^2) 的复杂性降低到至少 O(n log n)

Reducing complexity of O(n^2) to at least O(n log n)

c++

algorithm

time-complexity