Overview

This problem asks us to select a subset of the fundraising amounts of \(N\) given teams such that their sum is at least half of the total sum (at least \(\lceil T / 2 \rceil\)), and find the minimum number of teams required to achieve this.

Analysis

Key Observation

To minimize the number of selected teams, a greedy approach of “prioritizing teams with larger fundraising amounts” is optimal.

For example, consider 4 teams with fundraising amounts \([10, 20, 30, 40]\). The total sum is \(100\), so the target value is \(50\). - Selecting in ascending order: \(10 + 20 + 30 = 60\) (requires 3 teams) - Selecting in descending order: \(40 + 30 = 70\) (achieved with 2 teams)

Thus, to collect as much fundraising amount as possible in each step, it is most efficient to select the teams in descending order of their amounts.

Solution

1. Find the sum \(T\) of the fundraising amounts of all teams, and calculate the target value \(\lceil T / 2 \rceil\).
2. Sort the array \(A\) of fundraising amounts in descending order.
3. Add up the fundraising amounts starting from the beginning (the team with the largest amount) and stop as soon as the sum becomes greater than or equal to the target value. The number of teams selected up to that point is the answer.

Algorithm

1. While reading the input, calculate the total sum of the fundraising amounts total_sum.
2. Calculate the target value as target = (total_sum + 1) / 2 (this is the integer division representation of \(\lceil T / 2 \rceil\)).
3. Sort the array \(A\) in descending order.
4. Iterate through the sorted array to accumulate the values in descending order, and print the number of iterations (the number of selected teams) as soon as the cumulative sum becomes greater than or equal to target, then terminate.

Complexity

• Time Complexity: \(O(N \log N)\)
  • Calculating the total sum and scanning the cumulative sum takes \(O(N)\) time.
  • The bottleneck is sorting the array, which takes \(O(N \log N)\) time. Since \(N \le 10^6\), this easily fits within the time limit.
• Space Complexity: \(O(N)\)
  • We use an array of size \(N\) (std::vector in C++) to store the input fundraising amounts.

Implementation Details

• Preventing Overflow: Since \(N\) can be up to \(10^6\) and each \(A_i\) can be up to \(10^9\), the total fundraising amount \(T\) can reach up to \(10^{15}\). This significantly exceeds the maximum value of a standard 32-bit signed integer (around \(2 \times 10^9\) for int in C++), so you must use a 64-bit integer type (long long in C++).

• Ceiling Division: When calculating at least half of the total sum \(T\) (rounded up), using floating-point types (such as double) can cause precision issues. By performing the calculation using only integer arithmetic as (total_sum + 1) / 2, you can safely and accurately find the ceiling value.

• Fast I/O: Since the number of inputs is very large (\(N = 10^6\)), in C++, you can significantly reduce the execution time by using cin.tie(NULL) and ios_base::sync_with_stdio(false) to speed up the input/output operations.

  Source Code

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    if (!(cin >> N)) return 0;

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

    sort(A.rbegin(), A.rend());

    long long target = (total_sum + 1) / 2;
    long long current_sum = 0;
    int count = 0;

    for (int i = 0; i < N; ++i) {
        current_sum += A[i];
        count++;
        if (current_sum >= target) {
            break;
        }
    }

    cout << count << "\n";

    return 0;
}

This editorial was generated by gemini-3.5-flash-high.