Editorial for Battery Pack Merging

Use this editorial only when stuck, and do not 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$ .

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

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

Solution (Python)

Code 1

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)

Comments0

No comments yet

Be the first to comment.

Editorial for Battery Pack Merging

Approach

Solution (Python)

Comments0

New comment