【Codeforces Round #515 (Div. 3) D. Boxes Packing】 二分

D. Boxes Packing

题意

题意就是给你m个大小为k的盒子和n个大小为$a_i$的物品，用盒子装物品的方法是，能装下就装，并且容量减少$a_i$,否则就换下一个盒子（换下去的盒子不能再用），要求从左到右减少最少数量的物品，保证m个盒子按照这个方法能装下剩余的物品。

做法

很明显满足二分性质，二分+check就完事了！

代码

#include<stdio.h>
typedef long long ll;
const int maxn = 2e5+5;
ll a[maxn];
int n,m,k;
bool check(int mid)
{
    int tt=m-1;int tmp=k;for(int i=mid+1;i<=n;i++){
    if(tmp>=a[i]) tmp-=a[i];else{
    if(tt>0){
    tt--;tmp=k-a[i];}else return false;}}return true;
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=n;i++) scanf("%lld",&a[i]);int l=0,r=n,mid;while(l<=r){
    mid=(l+r)/2;if(check(mid)) r=mid-1;else l=mid+1;}printf("%d\n",n-l);return 0;
}