LeetCode P1182. 数列分段 Section II
原题链接
中等
作者:
我是java同学
,
2024-01-10 20:31:10
,
所有人可见
,
阅读 40
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100010;
int n, m;
int q[N];
bool check(int mid) {
LL sum = 0, cnt = 1;
//cnt必须从1开始,划三条线有四段
for (int i = 0; i < n; i ++ ) {
if (sum + q[i] > mid) {
sum = 0;
cnt ++ ;
}
sum += q[i];
}
return cnt <= m;
}
int main() {
scanf("%d%d", &n, &m);
int l = 0, r = 0;
for (int i = 0; i < n; i ++ ) {
scanf("%d", &q[i]);
l = max(l, q[i]);
r += q[i];
}
while (l < r) {
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
cout << r << endl;
return 0;
}