推 black80731: 要把 nums[i] 多出來的部分 04/06 07:30
→ black80731: 塞進馬來菊花要怎麼 寫 我英文很爛 謝謝 04/06 07:30
→ pandix: 馬來菊花.append(nums[i]) 04/06 07:37
推 NTHUlagka: 好強 04/06 08:33
→ Rushia: 大師 04/06 14:21
※ 引述《Rushia (みけねこ的鼻屎)》之銘言：
: 2439. Minimize Maximum of Array
: 給你一個陣列 nums ，你可以做無限次數的下列一串操作(必須同時做)：
: 1. i 必須滿足 1 <= i < n 且 nums[i] > 0
: 2.把 nums[i - 1] 遞增
: 3.把 nums[i] 遞減
: 試求經過多次操作後，陣列裡的最大值是多少? 這個最大值要盡可能小。
提供一個O(n)的做法:
假設已經知道nums[0~i-1]部分能達成的最小最大值 premax
nums[0~i-1] 都已經小於等於 premax
1.如果 premax >= nums[i]: premax 維持不變，因為 i-1 之前多出來的不能往右移
2.如果 premax < nums[i]: 嘗試把 nums[i] 多出來的部分分攤給全部人
其實可以直接看 nums[0~i] 的平均值是多少就好
如果這平均值 >= premax: 那新的 max 就會是這個平均值
如果這平均值 < premax: 前面的 nums[0~i-1] 已經告訴你他最小就是 premax 了
這種狀況 premax 就只能維持不變，可以參考 [10,1,1,1,11] 的結果
Python code:
class Solution:
def minimizeArrayValue(self, nums: List[int]) -> int:
premax = presum = 0
for i, num in enumerate(nums):
if premax < num:
premax = max(premax, ceil((presum+num) / (i+1)))
presum += num
return premax
--
沒人在乎
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.252.3.181 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1680737359.A.72B.html