如何将O(n²)复杂度的筹款计算程序优化至至少O(n log n)？

Alright, let's fix this performance bottleneck. The original code works correctly but will grind to a halt for large datasets (like the 200,000 elements hinted by the array size) thanks to its O(n²) nested loop. Here's how we can optimize it to O(n log n) while preserving full correctness:

Key Insight #

The optimal donation percentage must be one of the existing P values from participants. Here's why:

• If you pick a percentage higher than all P values, no one donates (total funds = 0).
• If you pick a percentage between two existing P values (say Pₐ > Pᵦ), you’ll get the same set of donors as using Pₐ but with a lower percentage—so total funds will be less than using Pₐ.
• This means we only need to evaluate each existing P value, but we can compute the total funds for each in constant time after sorting.

Optimization Steps #

1. Sort Participants: Sort all (salary, donation percentage) pairs in descending order of P. This way, for any element at position i, all elements from 0 to i have a P value ≥ the current element's P.
2. Prefix Sum Calculation: Compute a running total of salaries as we iterate through the sorted list. This lets us quickly get the sum of all salaries from participants who will donate when we choose the current P value.
3. Compute Maximum Funds: For each element in the sorted list, calculate total funds as (current P) * (prefix sum up to current index) / 100, and track the maximum value.

Optimized Code #

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

using namespace std;

struct Participant {
    long long salary;
    double p;
};

// Sort participants in descending order of donation percentage
bool compare(const Participant& a, const Participant& b) {
    return a.p > b.p;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n;
    cin >> n;
    
    vector<Participant> participants(n);
    for (int i = 0; i < n; ++i) {
        cin >> participants[i].salary >> participants[i].p;
    }
    
    // Sort to group higher donation percentages first
    sort(participants.begin(), participants.end(), compare);
    
    long long prefix_sum = 0;
    double max_funds = 0.0;
    
    for (const auto& participant : participants) {
        prefix_sum += participant.salary;
        double current_funds = participant.p * prefix_sum / 100.0;
        if (current_funds > max_funds) {
            max_funds = current_funds;
        }
    }
    
    cout << fixed << setprecision(20) << max_funds << endl;
    
    return 0;
}

Explanation #

• Sorting: The sort function runs in O(n log n) time, which is the dominant cost here—this is a massive improvement over the original O(n²) loop.
• Prefix Sum: We build the salary sum incrementally as we iterate, so this step is O(n) time.
• Max Calculation: Each iteration is O(1), making this step O(n) time overall.
• Fast I/O: We retain the original code's fast input/output optimizations to handle large datasets efficiently.

Testing this code with your sample input:

Input:
4
100001 83.2
40001 20
90001 77.32
300001 1.88

After sorting, participants are ordered by P descending:

1. (100001, 83.2) → funds = 83.2 * 100001 / 100 = 83200.832
2. (90001, 77.32) → funds = 77.32 * (100001 + 90001) / 100 = 146909.5464 (this is the maximum)
3. (40001, 20) → funds = 20 * (100001 + 90001 + 40001) / 100 = 46000.6
4. (300001, 1.88) → funds = 1.88 * total_sum / 100 = 10064.0752

Which matches the sample output perfectly.

内容的提问来源于stack exchange，提问作者Sip_