Overview

This problem asks for the minimum number of teams required to collect at least half of the total donations from all teams.
Since we want to reach the target amount with as few teams as possible, it is optimal to choose teams in descending order of their donation amounts.

Analysis

Let \(T\) be the total amount of donations from all teams. The condition is satisfied if the sum of the chosen teams is at least

\( \lceil T / 2 \rceil \)

or more.

The key point here is that if we want to minimize the number of teams, it is most efficient to choose teams with larger donation amounts first.

For example, suppose the donation amounts are

\(4, 3, 2, 1\)

The total is \(10\), so the target is \(5\).

• If we choose in descending order: \(4 + 3 = 7\), which takes \(2\) teams.
• If we choose in ascending order: \(1 + 2 + 3 = 6\), which takes \(3\) teams.

Thus, by prioritizing teams with larger amounts, we can minimize the number of teams needed.

Furthermore, the maximum amount we can collect with \(k\) teams is achieved by choosing the \(k\) largest donations.
Therefore, if choosing the \(k\) largest donations does not reach the target, no other combination of \(k\) teams will.

A naive approach of trying all combinations of teams would result in \(2^N\) possibilities.
Since the constraint is \(N \leq 10^6\), this approach will easily time out.

Thus, we sort the donation amounts in descending order and add them up from the largest to find the minimum number of teams.

Algorithm

1. Input \(N\) and the array \(A\).
2. Calculate the total donation amount \(T\) of all teams.
3. Set the target amount to \(target = \lceil T / 2 \rceil\).
   • When calculating with integers, this can be written as \(target = (T + 1) / 2\).
4. Sort the array \(A\) in descending order.
5. Add the values from the largest to the smallest.
6. Output the number of teams at the moment the sum becomes at least \(target\).

For example, consider the case where \(A = [2, 10, 3, 5]\).

The total is

\(2 + 10 + 3 + 5 = 20\)

so the target is

\(20 / 2 = 10\)

Sorting in descending order gives

\(10, 5, 3, 2\)

Adding from the beginning, we reach the target with just the first element \(10\), so the answer is \(1\).

Complexity

• Time Complexity: \(O(N \log N)\)
  • The most expensive part is sorting the array.
• Space Complexity: \(O(N)\)
  • To store the donation amounts in an array.

Implementation Details

The donation amount \(A_i\) is at most \(10^9\), and the number of teams \(N\) is at most \(10^6\).
Therefore, the total sum can be up to

\(10^9 \times 10^6 = 10^{15}\)

Since this does not fit in a standard 32-bit integer (int), the total sum and cumulative sums must be managed using a long long type.

Also, the target amount representing at least half can be calculated as:

long long target = (total + 1) / 2;

This correctly performs rounding up even when \(total\) is odd.

Source Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    vector<long long> A(N);
    long long total = 0;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        total += A[i];
    }

    sort(A.begin(), A.end(), greater<long long>());

    long long target = (total + 1) / 2;
    long long sum = 0;

    for (int i = 0; i < N; i++) {
        sum += A[i];
        if (sum >= target) {
            cout << i + 1 << '\n';
            return 0;
        }
    }

    return 0;
}

---

This editorial was generated by gpt-5.5-high.