M_sea

CF1066D Boxes Packing
CodeforcesLuogu分析显然,可行性关于扔的个数是单调的。也就是说,若扔$i$个可以,那扔$i+1$个也...
扫描右侧二维码阅读全文
20
2018/10

CF1066D Boxes Packing

Codeforces

Luogu

分析

显然,可行性关于扔的个数是单调的。

也就是说,若扔$i$个可以,那扔$i+1$个也一定可以。

所以可以二分扔的个数,答案即为总数减掉扔的个数。

判断可行性可以直接$O(n)$扫一遍。总时间复杂度$O(n \log n)$。

我竟然十分钟切了蓝题qwq

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

int n,m,k;
int a[200010];

inline int check(int q) {
    int filled=0,cnt=0;
    for (re int i=q+1;i<=n;i++) {
        if (cnt==m-1&&filled+a[i]>k) return 0;
        if (filled+a[i]>k) cnt++,filled=a[i];
        else filled+=a[i];
    }
    return 1;
}
        
int main() {
    n=read(),m=read(),k=read();
    for (re int i=1;i<=n;i++) a[i]=read();
    int L=0,R=n;
    while (L<R) {
        int mid=(L+R)>>1;
        if (check(mid)) R=mid;
        else L=mid+1;
    }
    printf("%d\n",n-L);
    return 0;
}
最后修改:2018 年 11 月 09 日 05 : 50 PM

发表评论