Summary

This problem asks for the minimum number of teams to select from \(N\) teams such that the sum of their donations is at least half of the total amount (i.e., at least \(\lceil T/2 \rceil\)).

Analysis

First, since we want to minimize the number of teams selected, it is intuitive that we should select teams that can efficiently collect as much money as possible.

The key observation here is that “it is always optimal to select teams in descending order of their donation amounts.”

This is because, for any fixed number of selected teams, prioritizing teams with larger donation amounts will yield a larger total sum. For example, if we choose \(k\) teams, choosing the top \(k\) teams with the largest amounts will maximize the sum among all possible combinations of size \(k\). Therefore, to achieve the target amount with the minimum number of teams, we should greedily select them from largest to smallest.

Let’s consider a concrete example. Suppose the donation amounts of the teams are \(\{1, 3, 5, 4, 2\}\). The total sum is \(T = 15\), and the target is \(\lceil 15/2 \rceil = 8\).

• Sorting in descending order gives \(\{5, 4, 3, 2, 1\}\)
• Select \(5\) \(\rightarrow\) total is \(5\) (still less than \(8\))
• \(5 + 4 = 9\) \(\rightarrow\) total is \(9\) (at least \(8\) achieved!)

Thus, the answer is \(2\) teams.

Note that we must be careful with the “at least half (\(\lceil T/2 \rceil\) or more)” condition when calculating the target amount. If \(T\) is odd, simply using \(T/2\) with integer division will round down, so we need to calculate \(\lceil T/2 \rceil\) correctly.

Algorithm

We can solve this problem with the following steps:

1. Find the total donation amount \(T\) of all teams.
2. Calculate the target amount \(\lceil T/2 \rceil\). In integer arithmetic, we can implement the ceiling function as (total + 1) // 2.
3. Sort the donation amounts in descending order.
4. Add the amounts one by one starting from the largest, and output the number of selected teams when the cumulative sum becomes greater than or equal to the target amount.

This is a typical application of the greedy algorithm.

Let’s verify why (total + 1) // 2 equals \(\lceil T/2 \rceil\): - When \(T\) is even (e.g., \(T=10\)): \((10+1)//2 = 5\), which matches \(\lceil 10/2 \rceil = 5\). - When \(T\) is odd (e.g., \(T=15\)): \((15+1)//2 = 8\), which matches \(\lceil 15/2 \rceil = 8\).

Complexity

• Time Complexity: \(O(N \log N)\) (dominated by sorting. Calculating the total sum and cumulative sums takes \(O(N)\))
• Space Complexity: \(O(N)\) (to store the input array)

Implementation Points

• Fast I/O: Since \(N\) can be up to \(10^6\), calling input() repeatedly can be slow. We can speed up the process by reading the entire input at once using sys.stdin.buffer.read() and then splitting and converting it.

• Handling the Ceiling Function: Since the condition is “at least half”, which is \(\lceil T/2 \rceil\), we implement the ceiling division as (total + 1) // 2. Note that using total // 2 will lead to incorrect results when \(T\) is odd.

• Descending Sort: We sort the array in descending order using a.sort(reverse=True) and then sum them up greedily.

• Guaranteed to Satisfy the Condition: If we select all teams, the sum will be \(T \geq \lceil T/2 \rceil\). Therefore, the condition is guaranteed to be met within the loop, and the answer will always be found.

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    a = [int(x) for x in data[1:1+n]]
    total = sum(a)
    half = (total + 1) // 2
    a.sort(reverse=True)
    s = 0
    cnt = 0
    for x in a:
        s += x
        cnt += 1
        if s >= half:
            break
    print(cnt)

main()

This editorial was generated by claude4.8opus-high.