题目链接：https://ac.nowcoder.com/acm/contest/886/D

题意：给n个物品，每个物品有一个体积值，K个箱子，问箱子的最小体积为多少可将物品全部装下。

思路：比赛时一看到题，就认定是二分，然后就wa了三小时。赛后知道这部满足二分的单调性，比如官方题解的例子：

　　

　　　正确做法是暴力枚举即可，答案下界为sum/K，上界为sum/K+maxv。上界证明如下：

　　

　　　对每一个答案的判断的复杂度为nlogn，所以总复杂度为O(maxv×nlogn)。

AC代码：

#include
#include
#include
using namespace std;

const int maxn=;
int T,n,K,cas,v[maxn];
vector vc;

int work(int x){
vc.clear();
vc.push_back();
for(int i=;i<=n;++i) vc.push_back(v[i]); vc.push_back(0x3f3f3f3f); int res=,num=; while(){ ++res; int now=x,ri=vc.size()-; while(){ int l=,r=ri,mid; while(l<=r){ mid=(l+r)>>;
if(vc[mid]<=now) l=mid+; else r=mid-; } if(!r) break; else{ now-=vc[r]; ++num; vector::iterator it=vc.begin()+r;
vc.erase(it);
if(now<vc[]) break;
ri=r-;
}
}
if(num==n) break;
}
return res;
}

int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&K);
int sum=;
for(int i=;i<=n;++i){ scanf("%d",&v[i]); sum+=v[i]; } sort(v+,v++n); if(K>=n){
printf("Case #%d: %d\n",++cas,v[n]);
continue;
}
int l=sum/K,r=sum/K+v[n];
for(int i=l;i<=r;++i)
if(work(i)==K){
printf("Case #%d: %d\n",++cas,i);
break;
}
}
return ;
}