AcWing 4178. 数列分段 II
原题链接
简单
作者:
Air1222
,
2024-04-10 15:54:31
,
所有人可见
,
阅读 7
//题目中要求每段连续,所以可以使用贪心策略
//sum记录当前段内的总和
//res记录总段数
//能放则放,不能放则开新组
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1e5+10;
int n,m;
LL a[N];
bool check(int mid)
{
LL sum=0;
int res=1;
for(int i=1;i<=n;i++)
{
if(sum+a[i]<=mid) sum+=a[i];
else
{
res++;
sum=a[i];
}
}
return res<=m;
}
int main()
{
cin>>n>>m;
LL l=0,r=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
l=max(l,a[i]);
r+=a[i];
}
while(l<r)
{
int mid=l+r>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
cout<<r;
return 0;
}