Summary

This problem asks for the minimum number of teams to select such that the sum of the donation amounts of the selected teams is at least half of the total donation amount of all teams, given the donation amounts of \(N\) teams.

Analysis

To minimize the number of selected teams, it is optimal to select the teams in descending order of their collected donation amounts.

This is because to achieve the target amount with fewer teams, having a larger donation amount per team is more advantageous. If we were to select a team with a smaller amount, replacing it with a team with a larger amount would allow us to achieve the target with the same or fewer teams.

Therefore, we can find the solution using a greedy approach (a method of repeatedly making the best choice at each step) by “selecting teams starting from the one with the largest donation amount.”

Algorithm

1. Calculate the total sum \(T\) of the donation amounts of all teams.
2. Calculate the target amount to achieve, which is \(\lceil T / 2 \rceil\).
3. Sort the list of donation amounts in descending order (largest to smallest).
4. Add up the amounts starting from the beginning of the sorted list, terminate the loop as soon as the sum becomes greater than or equal to the target amount, and output the number of teams at that point.

Complexity

• Time Complexity: \(O(N \log N)\) (sorting the list is the most time-consuming process)
• Space Complexity: \(O(N)\) (to store the list of input donation amounts)

Implementation Points

• Since the input constraint \(N \le 10^6\) is large, using the standard input() in Python may cause a Time Limit Exceeded (TLE) error just from reading the input. We can process the input quickly by using sys.stdin.buffer.read().split() to read all inputs at once.

• The target amount \(\lceil T / 2 \rceil\) is T // 2 + 1 when \(T\) is odd, and T // 2 when \(T\) is even. To express this easily in a program, writing (T + 1) // 2 allows us to perform the ceiling division in a single line.

• When sorting the list in descending order, use A.sort(reverse=True).

  Source Code

import sys

def solve():
    data = sys.stdin.buffer.read().split()
    N = int(data[0])
    A = [int(x) for x in data[1:N+1]]
    
    total = sum(A)
    target = (total + 1) // 2
    
    A.sort(reverse=True)
    
    cur = 0
    ans = 0
    for x in A:
        cur += x
        ans += 1
        if cur >= target:
            break
            
    print(ans)

if __name__ == "__main__":
    solve()

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