XTU 1244

二分
/*
这是一道二分题，主要的特点在于提到了“最大值最小”
基本思路是先不考虑分段次数，从最小的和枚举到最大的和，看哪个和满足指定分段次数m相等
最小的和：全部都分段，此时最小和为max(arr)
最大的和：只分一段，此时最大和为sum(arr)
其实可以在最小和和最大和直接直接遍历，但是为了加速，使用二分查找
对于left mid right分段的左右区间，有三种情况，若
分段数 > 指定分段次数 ， 说明指定的和太小，应该让和大点，才能让分段次数少点，
因此进入右区间left = mid + 1
分段数 = 指定分段次数 ， 此时分段数刚刚好，若是从小到大遍历，可直接退出，
但是倘若是二分查找，得继续往左区间看有没有更小的分段次数满足要求，因此right = mid -1
分段数 < 指定分段次数 ， 说明此时指定的和太大，导致分段数太少，因此要让和小一点，
因此进入左区间，right = mid -1
综合三种情况就有
当 分段数>指定分段次数，进入右区间
当 分段数<=指定分段次数，进入左区间
*/

#include
#includeusing 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;
} 

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！