題意#
題目給定一個包含 \( n \) 個正整數的陣列，要求將其切分為 \( k \) 個連續的子陣列。
目標是讓這些子陣列的總和之最大值越小越好。
我們需要求出能達成的最小「最大和」是多少。
思路#
「求最大值最小化」是標準的二分搜尋法（Binary Search）應用情境。
與其直接尋找切分位置，不如改變切入點：
若規定所有子陣列的和「不能超過」數值 \( m \)，我們最少會將陣列切成幾段？
這將尋找最佳切法的問題轉化為檢驗問題。
在掃描陣列時，我們採取貪婪策略，盡量將數字放入同一個子陣列。
當總和即將超過 \( m \) 時，才進行切分並開啟新的子陣列。
- 若段數不超過 \( k \)，表示上限 \( m \) 充裕，我們可以嘗試縮小 \( m \)。
- 若段數超過 \( k \)，表示上限 \( m \) 過低，需要提高 \( m \)。
二分搜的下界應為陣列中的「最大值」（確保單一元素能作為子陣列），
上界為「整個陣列的總和」（即不切分）。
我們在這兩個端點間進行二分搜尋，直到區間收斂。
程式碼#
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>
signed main() { WA();
int n, k; cin >> n >> k;
vector<int> v(n);
int total = 0, ans = 0;
// 讀入陣列同時計算總和，作為二分搜的上界
for (auto &i : v) cin >> i, total += i;
// l 為陣列最大值（下界），r 為陣列總和+1（上界）
for (int l = *max_element(all(v)), r = total+1; l < r;) {
// m 為這次嘗試的子陣列總和上限
int m = l + ((r-l) >> 1), cnt = 0, sum = 0;
// 貪心將數字塞入子陣列，超過 m 就切斷結算
for (auto &i : v) {
if (sum + i > m) {
sum = i;
cnt++;
}
else sum += i;
}
// 處理最後剩下的那段
cnt += sum > 0;
// 若段數不超過 k，表示上限 m 可行，嘗試縮小上限
if (cnt <= k) ans = r = m;
// 如果段數太多，代表 m 太嚴苛，必須提高
else l = m+1;
}
// 輸出達成條件的最小上限
cout << ans;
}
