對於給定的一個長度為N的正整數數列 A（1∼N），現要將其分成 M（M≤N）段，並要求每段連續，且每段和的最大值最小。
關於最大值最小：
例如一數列 4 2 4 5 1 要分成 3 段。
將其如下分段：
[4 2][4 5][1]
第一段和為 6，第 2 段和為 9，第 3段和為 1，和最大值為 9。將其如下分段：
[4][2 4][5 1]
第一段和為 4，第 2段和為 6，第 3 段和為 6，和最大值為 6。
並且無論如何分段，最大值不會小於 6。
所以可以得到要將數列 4 2 4 5 1 要分成 3 段，每段和的最大值最小為 6
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
int n, m;
long long a[100005] = {0};
long long sum = 0, maxa = 0;
bool check(long long k)
{
long long cnt = 1, temp = 0;
for(int i = 1;i <= n;i++)
{
if(temp + a[i] > k)
{
cnt++;
temp = a[i];
}
else
temp += a[i];
}
return cnt <= m;
}
int main()
{
cin >> n >> m;
for(int i = 1;i <= n;i++)
{
cin >> a[i];
sum += a[i];
maxa = max(maxa, a[i]);
}
long long low = maxa, high = sum;
long long ans;
while(low <= high)
{
long long mid = (low + high) / 2;
if(check(mid))
{
ans = mid;
high = mid - 1;
}
else
low = mid + 1;
}
cout << ans << endl;
return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
int n, m;
long long a[100005] = {0};
long long sum = 0, maxa = 0;
bool check(long long k)
{
long long cnt = 1, temp = 0;
for(int i = 1;i <= n;i++)
{
if(temp + a[i] > k)
{
cnt++;
temp = a[i];
}
else
temp += a[i];
}
return cnt <= m;
}
int main()
{
cin >> n >> m;
for(int i = 1;i <= n;i++)
{
cin >> a[i];
sum += a[i];
maxa = max(maxa, a[i]);
}
long long low = maxa, high = sum;
long long ans;
while(low <= high)
{
long long mid = (low + high) / 2;
if(check(mid))
{
ans = mid;
high = mid - 1;
}
else
low = mid + 1;
}
cout << ans << endl;
return 0;
}