题目链接：https://vjudge.net/problem/POJ-3273
题意：给定n个数，将这n个数划分成m块，问所有块最大值的最小是多少。
思路：注意到所求值最大为109，所以可以用二分来解这道题，输入过程得到n个数的和Sum，n个数中最大值Max，则[Max,Sum]即为二分区间。复杂度为O(nlogn)。
AC代码：
#include<cstdio> using namespace std; int n,m,a[100005],Max,Sum; int getm(int x){ int ret=1,k=1,tmp=a[0]; while(k<n){ if(tmp+a[k]<=x) tmp+=a[k++]; else ++ret,tmp=a[k++]; } return ret; } int main(){ scanf("%d%d",&n,&m); for(int i=0;i<n;++i){ scanf("%d",&a[i]); Sum+=a[i]; if(a[i]>Max) Max=a[i]; } int l=Max,r=Sum,mid; while(l<=r){ mid=(l+r)>>1; printf("%d\n",mid); if(getm(mid)>m) l=mid+1; else r=mid-1; } printf("%d\n",mid); return 0; }
原文：https://www.cnblogs.com/FrankChen831X/p/10739985.html