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

Great question! Let's break down how to fix that O(n²) bottleneck and get your solution running efficiently even for large input sizes.

Key Insight to Simplify the Problem #

The optimal donation percentage has to be one of the participants' maximum allowed percentages. Here's why: if you pick a random percentage x that isn't in the list of P[i], you can safely increase x to the next highest P[i] value—this will either keep your total funds the same (if no new participants qualify) or increase it (if more participants can now donate). So we only need to evaluate each P[i] as a candidate for the optimal percentage.

Optimization Strategy #

1. Sort participants by their max percentage (descending): This way, when we consider a percentage P[i], every participant before (and including) i has a max percentage >= P[i]—meaning they all qualify to donate at this rate.
2. Track prefix sums of salaries: As we iterate through the sorted list, we maintain a running total of salaries. For each position i, this sum represents the total salary of everyone who can donate at P[i].
3. Calculate and compare totals: For each candidate percentage, compute the total funds by multiplying the prefix sum by P[i]/100, then keep track of the highest value.

This approach cuts the time complexity to O(n log n) (from sorting) plus O(n) (for the prefix sum and calculation)—exactly what you're targeting.

Optimized C++ Code #

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

using namespace std;

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

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

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].max_pct;
    }
    
    sort(participants.begin(), participants.end(), compare);
    
    long long prefix_sum = 0;
    double max_funds = 0.0;
    
    for (const auto& p : participants) {
        prefix_sum += p.salary;
        double current_funds = prefix_sum * p.max_pct / 100.0;
        if (current_funds > max_funds) {
            max_funds = current_funds;
        }
    }
    
    cout << fixed << setprecision(20) << max_funds << endl;
    
    return 0;
}

Code Breakdown #

• Struct & Sorting: The Participant struct pairs each salary with its max percentage, and we sort the list from highest to lowest percentage to group eligible donors together.
• Prefix Sum with long long: We use a 64-bit integer for the prefix sum to avoid overflow—with salaries up to 300,000 and 200,000 participants, the total sum can reach 6e10, which is way beyond 32-bit integer limits.
• Efficient Calculation: For each sorted participant, we add their salary to the running total, compute the funds for their percentage, and update the maximum if this value is higher.

Testing with Your Example Input #

Input:

4
100001 83.2
40001 20
90001 77.32
300001 1.88

After sorting descending by max percentage:

1. 100001, 83.2 → prefix sum = 100001 → funds = 83200.832
2. 90001, 77.32 → prefix sum = 190002 → funds = 146909.5464 (this is the maximum)
3. 40001, 20 → prefix sum = 230003 → funds = 46000.6
4. 300001, 1.88 → prefix sum = 530004 → funds = 9964.0752

The output matches your example perfectly: 146909.5464.

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