Overview

This problem asks us to find the minimum number of teams required to collect at least half of the total donation amount of all teams, given the donation amounts of \(N\) teams.

Analysis

• Drawbacks of a Naive Approach: If we try all possible combinations of teams to choose (e.g., using bit brute-force search), the time complexity becomes \(O(2^N)\). With the constraint \(N \leq 10^6\), this will not finish within the time limit and will result in TLE (Time Limit Exceeded).
• Key Observation: Considering the goal of “achieving the target amount with as few teams as possible”, it is advantageous to choose teams with larger donation amounts. Therefore, we can intuitively see that the optimal strategy is to select teams in descending order of their donation amounts.
• Proof of Correctness for the Greedy Approach: If we were to choose a team with a smaller amount instead of one with a larger amount, we would need either more teams or at best the same number of teams to reach the target. Therefore, using a greedy approach where we sort the amounts in descending order and sum them up sequentially guarantees finding the minimum number of teams.

Algorithm

1. Calculate the total donation amount \(T\) of all teams.
2. Calculate the target amount to be eligible for award, \(\text{half} = \lceil T / 2 \rceil\). To handle cases where \(T\) is odd, we can represent the ceiling division using integer arithmetic as (T + 1) / 2.
3. Sort the donation amounts \(A_i\) of each team in descending order (from largest to smallest).
4. Iterate through the sorted array from the beginning and accumulate the sum.
5. Stop the process as soon as the accumulated sum becomes greater than or equal to \(\text{half}\), and output the number of teams selected up to that point.

Complexity

• Time Complexity: \(O(N \log N)\) (sorting the array is the bottleneck)
• Space Complexity: \(O(N)\) (space required to store the array)

Implementation Details

• Since the donation amount \(A_i\) can be up to \(10^9\) and the number of teams \(N\) can be up to \(10^6\), the total amount \(T\) can reach up to \(10^{15}\). Since this will overflow a 32-bit integer type (such as int in C++), you must use a 64-bit integer type (such as long long).

• To calculate the target amount \(\lceil T / 2 \rceil\), we need to round up if T is odd. By writing it as (T + 1) / 2, we can accurately represent the ceiling division using only integer division.

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N;
    cin >> N;
    vector<long long> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }
    
    long long T = accumulate(A.begin(), A.end(), 0LL);
    long long half = (T + 1) / 2; // ceil(T / 2)
    
    sort(A.begin(), A.end(), greater<long long>());
    
    long long sum = 0;
    int cnt = 0;
    for (int i = 0; i < N; ++i) {
        sum += A[i];
        cnt++;
        if (sum >= half) {
            break;
        }
    }
    
    cout << cnt << "\n";
    
    return 0;
}

This editorial was generated by or-glm5.2-high.