題目連結:
題目意譯:
你一開始有著初始力量值 power、一個初始分數值 0,以及一袋代幣 tokens,其中 tokens[i] 為第 i 個代幣的數值(索引值從 0 開始)。
你的目標是對每個代幣,可能藉由下列兩種方式之一來遊玩,以最大化你的分數:
如果你當前的力量值至少是 tokens[i],你可以把第 i 個代幣面朝上地來遊玩,失去 tokens[i] 點力量值並得到 1 點分數。
如果你當前的力量值至少是 1,你可以把第 i 個代幣面朝下地來遊玩,獲得 tokens[i] 點力量值並失去 1 點分數。
每個代幣最多只能玩一次,並且可以任意順序遊玩。你不需要使用掉所有代幣。
回傳你使用若干數量的代幣後可以得到的最大分數值。
限制:
0 ≦ tokens.length ≦ 1000
0 ≦ tokens[i], power < 10 ^ 4
範例測資:
範例 1:
輸入: tokens = [100], power = 50
輸出: 0
解釋: 用袋子中唯一一個代幣來遊玩是不行的,因為你要嘛力量值太低、要嘛分數值太低。
範例 2:
輸入: tokens = [100,200], power = 150
輸出: 1
解釋: 將第 0 個代幣(100)面朝上地來遊玩,你的力量值變成 50 而分數值變成 1。
不需要使用第 1 個代幣,因為你沒辦法藉由將其面朝上地來遊玩,並增加你的分數。
範例 3:
輸入: tokens = [100,200,300,400], power = 200
輸出: 2
解釋: 以下列順序遊玩各個代幣,將得到分數值 2:
1. 將第 0 個代幣(100)面朝上地來遊玩,你的力量值變成 100 而分數值變成 1。
2. 將第 3 個代幣(400)面朝下地來遊玩,你的力量值變成 500 而分數值變成 0。
3. 將第 1 個代幣(200)面朝上地來遊玩,你的力量值變成 300 而分數值變成 1。
4. 將第 2 個代幣(300)面朝上地來遊玩,你的力量值變成 0 而分數值變成 2。
解題思維:
可以看到把數值小的代幣盡量朝上、數值大的代幣盡量朝下將會是最佳的策略,其中「盡量」代表著的是只要力量值夠玩當前最小的代幣面朝上則就面朝上;否則如果袋子中還有兩個代幣的話,則把數值最大的代幣面朝下來玩。
因此就按照上面的策略來玩即可(可以先將 tokens 中的數字由小排到大以便存取當前最小和當前最大)。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。