給出一個數(shù)列,每一次操作可以將其中一個數(shù)換成兩個數(shù),兩數(shù)之和和原數(shù)一樣,問最少幾次操作可以將數(shù)列變成單調不減,貪心思想,最后一個數(shù)作為初始值,如果前一個數(shù)比他大,盡量分裂成更大更相等的幾個數(shù),不斷和前一個數(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