給出一個(gè)數(shù)列，每一次操作可以將其中一個(gè)數(shù)換成兩個(gè)數(shù)，兩數(shù)之和和原數(shù)一樣，問最少幾次操作可以將數(shù)列變成單調(diào)不減，貪心思想，最后一個(gè)數(shù)作為初始值，如果前一個(gè)數(shù)比他大，盡量分裂成更大更相等的幾個(gè)數(shù)，不斷和前一個(gè)數(shù)比直到數(shù)列頭
1 #2366
2 #Runtime: 432 ms (Beats 100%) Sorry, there are not enough accepted submissions to show data
3 #Memory: 25.8 MB (Beats 100%) Sorry, there are not enough accepted submissions to show data
4
5 class Solution(object):
6 def minimumReplacement(self, nums):
7 """
8 :type nums: List[int]
9 :rtype: int
10 """
11 pre = nums[-1]
12 ans = 0
13 for i in range(len(nums) - 1, -1, -1):
14 d = nums[i] // pre
15 if nums[i] % pre != 0:
16 d += 1
17 ans += d - 1
18 pre = nums[i] // d
19 return ans