博客

二分

/*

这是一道二分题，主要的特点在于提到了“最大值最小”

基本思路是先不考虑分段次数，从最小的和枚举到最大的和，看哪个和满足指定分段次数m相等

最小的和：全部都分段，此时最小和为max(arr)

最大的和：只分一段，此时最大和为sum(arr)

其实可以在最小和和最大和直接直接遍历，但是为了加速，使用二分查找

对于left mid right分段的左右区间，有三种情况，若

分段数 > 指定分段次数 ， 说明指定的和太小，应该让和大点，才能让分段次数少点，

因此进入右区间left = mid + 1

分段数 = 指定分段次数 ， 此时分段数刚刚好，若是从小到大遍历，可直接退出，

但是倘若是二分查找，得继续往左区间看有没有更小的分段次数满足要求，因此right = mid -1

分段数 < 指定分段次数 ， 说明此时指定的和太大，导致分段数太少，因此要让和小一点，

因此进入左区间，right = mid -1

综合三种情况就有

当 分段数>指定分段次数，进入右区间

当 分段数<=指定分段次数，进入左区间

*/

#include<iostream>
#include<algorithm>

using namespace std;
typedef long long LL;
const int maxn=1e4+10;
int t;
int n,m;
LL l,r,ans; 
LL ch[maxn];
int check(LL x){
	LL t=0;
	int tag=0;
	for(int i=0;i<n;i++){
		t+=ch[i];
		if(t>x){
			t=ch[i];
			tag++;
		}
	}
	tag++;
	return tag;
}
int main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>t;
	while(t--){
		cin>>n>>m;
		l=0,r=0;
		for(int i=0;i<n;i++){
			cin>>ch[i];
			l=max(l,ch[i]);
			r+=ch[i];
		}
		while(l<=r){
			LL mid=l+(r-l)/2;
			if(check(mid)>m){
				l=mid+1;
			}
			else{
				r=mid-1;
			}
		}
		cout<<l<<endl;
	}
	return 0;
}