最小可能的「最大段和」-- 二分搜應用

題目（Problem） 給定一個長度為 n 的正整數陣列 A[0..n-1]，你要把它切成 恰好 k 段連續子陣列（k ≤ n）。定義每段的「段和」為該段元素總和。目標是最小化所有段和中的最大值。 必須保持原來順序、只能切割、段與段不可交錯（連續切段）。 回傳（或輸出）。 def can_split(A, k, cap): """在每段和 ≤ cap 的限制下，最少需要幾段；是否 ≤ k。""" segments = 1 cur = 0 for x in A: if cur + x <= cap: cur += x else: segments += 1 cur = x if segments > k: # 及早停止 return False return True # 需要的段數 ≤ k def minimize_largest_sum(A, k): lo, hi = max(A), sum(A) # 下界：至少要容得下最大元素；上界：全部一段 ans = hi while lo <= hi: mid = (lo + hi) // 2 if can_split(A, k, mid): # mid 可行 → 嘗試更小 ans = mid hi = mid - 1 else: # mid 不可行 → 增大容量 lo = mid + 1 return ans A ,k = [7, 2, 5, 10, 8], 2 print(minimize_largest_sum(A, k)) A ,k = [7, 2, 5, 10, 8], 3 print(minimize_largest_sum(A, k)) # Output: # 18 # 14