Maximum Coins Heroes Can Collect
|
|
Explanation
The code is a Python solution to a problem where you are given three lists: heroes
, monsters
, and coins
. The goal is to find, for each hero, the maximum number of coins you can collect by defeating monsters that the hero can beat.
Details
Initialization:
mon_cost
sorts themonsters
andcoins
together. This way, you know how many coins each monster yields.ps
is a prefix sum array, whereps[i]
will contain the sum of coins for defeating the firsti
monsters.res
is the list that will hold the maximum coins that each hero can collect.
Calculate Prefix Sum for Monsters:
- Loop through
mon_cost
and fill theps
array. It will help in quickly finding the total coins for a range of monsters.
- Loop through
Find Maximum Coins for Each Hero:
- For each hero
h
, use binary search to find the strongest monster that the hero can beat. - Append the maximum coins corresponding to that monster to
res
.
- For each hero
Steps
Sort Monsters with Their Coin Value:
1
mon_cost = sorted(list(zip(monsters, coins)))
- Zips
monsters
andcoins
and sorts them based on monster strength.
- Zips
Calculate Prefix Sum for Monsters’ Coins:
1 2 3
ps = [0] for _, c in mon_cost: ps.append(ps[-1] + c)
- Adds up coins as you loop through sorted
mon_cost
, storing them inps
.
- Adds up coins as you loop through sorted
Binary Search for Each Hero:
1 2 3 4 5 6 7 8
for h in heroes: l, r = 0, len(monsters) - 1 while l <= r: m = (l + r) // 2 if mon_cost[m][0] > h: r = m - 1 else: l = m + 1
- For each hero, this binary search finds the index
l
of the strongest monster they can defeat.
- For each hero, this binary search finds the index
Append Coins to Result:
1
res.append(ps[l])
- Using index
l
,ps[l]
gives us the maximum coins a hero can collect. We append it tores
.
- Using index
Return Result:
1
return res
- Return the
res
list, which contains the answer for each hero.
- Return the
Key Takeaways
- The use of sorting and prefix sum optimizes the problem.
- Binary search helps to find the range of monsters a hero can defeat quickly.
- Prefix sum allows for constant-time lookup to find the sum of coins a hero can collect.
This code is a good example of combining multiple techniques like sorting, prefix sum, and binary search to solve a problem efficiently.