ETH官方钱包

前往
大廳
主題

LeetCode - 2383. Minimum Hours of Training to Win a Competition 解題心得

Not In My Back Yard | 2023-07-12 12:00:16 | 巴幣 2 | 人氣 162

題目連結:


題目意譯:
你進入了一個競賽,而被給定兩個正整數 initialEnergy 和 initialExperience,依序代表著你一開始最初的能量值以及最初的經驗值。

你同時也被給定兩個索引值從 0 開始的整數陣列 energy 和 experience,兩者長度都為 n。

你將依序面對 n 位對手。第 i 位對手的能量值和經驗值依序以 energy[i] 和 experience[i] 所表示。當你面對一位對手時,你的經驗值和能量值需要都嚴格大於對手的才能打敗他們,並移動至下一位對手的面前(如果有的話)。

打敗第 i 位對手會使你的經驗值增加 experience[i],但你的能量值將減少 energy[i]。

在開始競賽之前,你可以訓練自己若干個小時。在每一小時的訓練中,你可以選擇將你的初始經驗值增加 1,又或是將你的初始能量值增加 1。

回傳要打敗所有對手最少所需的訓練時數。

限制:
n == energy.length == experience.length
1 ≦ n ≦ 100
1 ≦ initialEnergy, initialExperience, energy[i], experience[i] ≦ 100



範例測資:
範例 1:
輸入: initialEnergy = 5, initialExperience = 3, energy = [1,4,3,2], experience = [2,6,3,1]
輸出: 8
解釋: 你可以在 6 小時的訓練後,將能量值增加到 11;並在 2 小時的訓練後,將經驗值增加至 5。
你將按照以下順序面對各個對手:
- 你有著比第 0 號對手更多的能量和經驗值,所以你贏。
  你的能量值變成 11 - 1 = 10,而你的經驗值變成 5 + 2 = 7。
- 你有著比第 1 號對手更多的能量和經驗值,所以你贏。
  你的能量值變成 10 - 4 = 6,而你的經驗值變成 7 + 6 = 13。
- 你有著比第 2 號對手更多的能量和經驗值,所以你贏。
  你的能量值變成 6 - 3 = 3,而你的經驗值變成 13 + 3 = 16。
- 你有著比第 3 號對手更多的能量和經驗值,所以你贏。
  你的能量值變成 3 - 2 = 1,而你的經驗值變成 16 + 1 = 17。
你在競賽前,總計進行了 6 + 2 = 8 小時的訓練,所以我們回傳 8。
可以證明更小的答案並不存在。

範例 2:
輸入: initialEnergy = 2, initialExperience = 4, energy = [1], experience = [3]
輸出: 0
解釋: 你不需要額外的能量或經驗便可以贏得這場競賽,所以我們回傳 0。


解題思維:
你只要直接掃過每一位對手,然後判斷當時的經驗值和能量值夠不夠打敗對手。如果不行,則代表你一開始需要額外的訓練。

假設是經驗值不夠,設現在其值為 x,而現在對手的經驗值則是 y,則你需要在一開始加上額外的 y - x + 1 小時來增加經驗值;如果是能量值的情況則也是類似。

因此掃完之後你便可以知道一開始需要多少訓練時數,此即為所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作