#2383
Minimum Hours of Training to Win a Competition
pupil · 530 · lc easy +28 · verified · 42.4% accepted · 386 likes · top 23%
Description
Before entering a competition, you start with initialEnergy energy and initialExperience experience. You face n opponents sequentially; opponent i has energy[i] energy and experience[i] experience.
To defeat opponent i you must have strictly more than their energy and strictly more than their experience. Winning adds experience[i] to yours and subtracts energy[i] from yours.
You may train beforehand: each hour adds one unit to either your energy or experience.
Return the minimum training hours needed to guarantee victory over all opponents.
Example 1:
Input: initialEnergy = 5, initialExperience = 3, energy = [1,4,3,2], experience = [2,6,3,1]
Output: 8
Explanation: You can increase your energy to 11 after 6 hours of training, and your experience to 5 after 2 hours of training.
You face the opponents in the following order:
- You have more energy and experience than the 0th opponent so you win.
Your energy becomes 11 - 1 = 10, and your experience becomes 5 + 2 = 7.
- You have more energy and experience than the 1st opponent so you win.
Your energy becomes 10 - 4 = 6, and your experience becomes 7 + 6 = 13.
- You have more energy and experience than the 2nd opponent so you win.
Your energy becomes 6 - 3 = 3, and your experience becomes 13 + 3 = 16.
- You have more energy and experience than the 3rd opponent so you win.
Your energy becomes 3 - 2 = 1, and your experience becomes 16 + 1 = 17.
You did a total of 6 + 2 = 8 hours of training before the competition, so we return 8.
It can be proven that no smaller answer exists.
Example 2:
Input: initialEnergy = 2, initialExperience = 4, energy = [1], experience = [3]
Output: 0
Explanation: You do not need any additional energy or experience to win the competition, so we return 0.
Code
1
2
3