Editorial for Battery Pack Merging

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Approach

Sort the battery packs from largest to smallest, then keep taking packs in that order until the running total is at least $T$ ~T~.

If the sum of all packs is still below $T$ ~T~, the answer is -1.

Time complexity is $O(n \log n)$ ~O(n \log n)~.

Solution (Python)

import sys


data = [int(x) for x in sys.stdin.buffer.read().split()]
n = data[0]
target = data[1]
capacities = data[2 : 2 + n]

capacities.sort(reverse=True)

charge = 0
for used, capacity in enumerate(capacities, start=1):
    charge += capacity
    if charge >= target:
        print(used)
        break
else:
    print(-1)

Comments

There are no comments at the moment.