40分萌新求助
查看原帖
40分萌新求助
1000187
nghd666666楼主2024/12/1 16:51
#include <bits/stdc++.h>
using namespace std;
long long k=1,n,tmax,d[15888],wt[15888];
bool cmp(long long a,long long b){
	return (a>b);
}
int check(long long sz){
	for(int i=1;i<=n;i++){
		wt[i]=0;
	}
	for(int i=1;i<=n;i++){
		long long j=0;
		while(1){
			j++;
			if(j>sz){
				return 0;
			}
			if(d[i]+wt[j]<=tmax){
				wt[j]+=d[i];
				break;
			}
		}
//		cout<<"j:"<<j<<endl;
	}
	return 1;
}
int main(){
	cin>>n>>tmax;
	for(int i=1;i<=n;i++){
		cin>>d[i];
	}
	sort(d+1,d+1+n,cmp);
	long long l=1,r=n,mid;
	while(l<=r){
		mid=(l+r)/2;
//		cout<<l<<" "<<r<<" "<<mid<<"\n";
		if(check(mid)){
			k=mid;
			r=mid-1;
		}else{
			l=mid+1;
		}
	}
	cout<<k;
    return 0;
}

2024/12/1 16:51
加载中...