Posted on 2023-07-09 04:02
Uriel 閱讀(62)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
貪心 、
閑來無事重切Leet Code 、
排序
給出一堆石子的重量，分到k個(gè)包里，每個(gè)包需要i～j連續(xù)堆全部取完，每堆的cost為weights[i]+weights[j]，求不同的分配方式里面k堆的總cost最大值和最小值之差
思路參考 -> https://leetcode.com/problems/put-marbles-in-bags/solutions/3734284/sort-video-solution/
1 #2551
2 #Runtime: 758 ms (Beats 16.67%)
3 #Memory: 25.1 MB (Beats 16.67%)
4
5 class Solution(object):
6 def putMarbles(self, weights, k):
7 """
8 :type weights: List[int]
9 :type k: int
10 :rtype: int
11 """
12 n = len(weights)
13 p = [0] * (n - 1)
14 for i in range(1, n):
15 p[i - 1] = weights[i] + weights[i - 1]
16 p.sort()
17 minx, maxx = 0, 0
18 for i in range(k - 1):
19 minx += p[i]
20 maxx += p[n - i - 2]
21 return maxx - minx