输入时处理出最小的答案和最大的答案,然后二分答案即可。
其余细节看代码
#include <iostream>
#include <cstdio> using namespace std; int n, m, a[], x, y, ans = ; bool pd(int mid)
{
int i, sum = , tot = ;
for(i = ; i <= n; i++)
{
sum += a[i];
if(sum > mid)//分段数+1
{
sum = a[i];
tot++;
}
}
if(tot > m) return ;
return ;//如果是小于m的话也还可以再分
} int main()
{
int i, j, mid;
scanf("%d %d", &n, &m);
for(i = ; i <= n; i++)
{
scanf("%d", &a[i]);
x = max(x, a[i]);//答案最小
y += a[i];//答案最大
}
while(x <= y)
{
mid = (x + y) >> ;
if(pd(mid)) y = mid - ;
else x = mid + ;
}
printf("%d", x);
return ;
}