解题思路
这道题目要求将一个正整数数列分成M个连续段，使得各段和的最大值最小。这是一个典型的二分查找应用问题，我们需要找到满足条件的最小最大值。
方法思路
二分查找：在可能的最大值范围内进行二分查找
检查函数：对于每个中间值mid，检查是否能将数列分成不超过M段，且每段和不超过mid
边界确定：左边界L设为数列中的最大值，右边界R设为数列总和
代码注释
#include
#define ll long long // 定义长整型别名
using namespace std;
const int N = 1e5 + 10;
ll n,m,a[N]; // n-数列长度，m-分段数，a-存储数列
ll L,R; // 二分查找的左右边界
// 检查函数：判断是否能在每段和不超过mid的情况下分成不超过m段
bool check(ll mid)
{
if(a[1] > mid) return 0; // 第一个数就超过mid，直接返回false
ll num = a[1]; // 当前段的和
ll sum = 1; // 当前分段数
for(int i = 2; i <= n; i++)
{
if(a[i] + num <= mid){ // 可以加入当前段
num += a[i];
}
else { // 需要新开一段
num = a[i];
sum++;
}
}
return sum <= m; // 判断分段数是否满足要求
}
int main()
{
cin >> n >> m; // 读取数列长度和分段数
for(int i = 1; i <= n; i++){
cin >> a[i]; // 读取数列元素
L = max(L,a[i]); // 更新左边界(单个元素最大值)
R += a[i]; // 更新右边界(数列总和)
}
ll ans;
while(L <= R){ // 二分查找
ll mid = (L + R) / 2;
if(check(mid)){ // 满足条件
ans = mid; // 更新答案
R = mid - 1; // 尝试更小的最大值
}
else L = mid + 1; // 需要更大的最大值
}
cout << ans; // 输出结果
return 0;
}