Problem Description
给定\(n\)个正整数\(a_1,a_2,\dots,a_n\)，将这个序列从左到右划分成\(m\)段，使得每段至少有一个数。
你需要让数字之和最大的那一段的数字和尽可能得小。
Input
第一行包含一个正整数
T(1≤T≤10)，表示测试数据的组数。
每组数据第一行包含两个正整数
n,m(1≤m≤n≤100000)。
第二行包含
n个正整数
(1≤ai≤10^9)。
Output
对于每组数据输出一行一个整数，即你找到的方案中，数字之和最大的那一段的数字和。
输入样例
1
6 4
1 5 4 6 2 3
输出样例
6
数学-构造单调函数二分
设函数f(x)表示数字和不大于x至少需要分成f(x)段，则二分寻找最小的x，使得f(x)等于m，注意f(x)相等时如何寻找最小的x
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int n,m;
int a[N];
ll f(ll x)
{
ll res=0,cnt=1;
for(int i=1;i<=n;++i)
{
if(res+a[i]>x) cnt++,res=0;
res+=a[i];
}
return cnt;
}
ll bina(ll mi,ll ma)//二分的目的:找到最小的x使得f(x)=m
{
ll l=mi,r=ma,ans=ma;
while(l<=r)
{
ll mid=(l+r)>>1;
ll tmp=f(mid);
//cout<<mid<<' '<<tmp<<'\n';
if(tmp<=m) ans=mid,r=mid-1;//现在想取的是最小的解不断让r向左逼近
else l=mid+1;
}
return ans;
}
void solve()
{
cin>>n>>m;
int maxn=0;
ll sum=0;
for(int i=1;i<=n;++i)
{cin>>a[i];maxn=max(maxn,a[i]);sum+=a[i];}
cout<<bina((ll)maxn,sum)<<"\n";
//cout<<f(6)<<"\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin>>T;
while(T--)
{
solve();
}
return 0;
}