Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
642 B
3
Indexable
Never
void solve(){
    ll n,W;cin>>n>>W;
    ipar(w,n);
    ll sum=accumulate(all(w),0);
    vector<ll>pre(n+1,0);
    for(int i=1;i<=n;i++)
        pre[i]=pre[i-1]+w[i-1];

    ll ans=0,h=0;
    while(ans<n){
        ll s=ans+1,e=n-1;
        while(s<=e){
            ll mid=(s+e+1)>>1;
            if(pre[mid]-pre[ans]<=W){
                ans=mid;
                s=mid+1;
            }else{
                e=mid-1;
            }
        }
        h++;
    }
    cout<<h+1<<"\n";
}





signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    ll t;
	cin>>t;
	while(t--) solve();
}
Leave a Comment