簡易題敘#
有個含 \(n\) ( \(1 \le n \le 10^5\) ) 個數字的陣列 \(a\) ( \(1 \le a_i \le 10^9\) ) ，你要把他切成 \(k\) 段 ( \(1 \le k \le n \le 10^5\) ) ，你要讓這些區段的最大和盡量小，求這些被你切割的區段最大和為多少。
範例測資：
- 輸入
10 4
1 3 2 4 10 8 4 2 5 3
- 輸出
12
概念講解#
既然我們要讓這些區段的最大和盡量小，那不如就拿「區段的最大和」二分搜，一定有某個數字，區段的最大和小於它的時候怎麼切都會超過 \(k\) 段，大於等於它的時候可以滿足切最多 \(k\) 段就能獲得這個和，也就是我們要求的「盡量小的區段最大和」。
check函式的部分，用 \(now\) 紀錄當前區段總和，若超過區段最大和限制 \(sum\) ，就記錄一個新的區段和，區段總數 \(cnt\) 加一，這邊要注意如果陣列裡有數超過 \(sum\)，那它一個數一個區間就已經違反規定了，直接 return 0。最後再檢查有沒有切超過 \(k\) 段即可。
範例程式碼#
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5;
int n, k, a[N];
bool check(int sum) {
int now = 0, cnt = 1;
for (int i = 0; i < n; i++) {
if (a[i] > sum) return 0;
if (now + a[i] > sum) {
now = a[i];
cnt++;
}
else now += a[i];
}
return cnt <= k;
}
signed main() {
cin >> n >> k;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int l = 0, r = 1e14 + 1; // 左開右開
while (r != l + 1) {
int mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid;
}
cout << r << '\n';
}
