一个小疑问
查看原帖
一个小疑问
917683
rnf5114楼主2023/7/24 19:40
#include <iostream>
using namespace std;
int n,m;
int a[300010],Max=-1,ans=1e9+10;
void bin(int l,int r){
	int mid=(l+r)/2,sum=0;
	if(l>r){
		return ;
	}
	for(int i=1;i<=m;i++){
		int tmp=a[i];
		while(tmp){
			if(tmp>=mid){
				tmp-=mid;
				sum++;
			}
			else{
				tmp=0;
				sum++;
				break;
			}
		}
	}
	if(sum<=n){
		ans=min(ans,mid);
		bin(l,mid-1);
	}
	else{
		bin(mid+1,r);
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>a[i];
		Max=max(Max,a[i]);
	}
	bin(0,Max);
	cout<<ans;
}

原代码,TLE#6

#include <iostream>
using namespace std;
int n,m;
int a[300010],Max=-1,ans=1e9+10;
void bin(int l,int r){
	int mid=(l+r)/2,sum=0;
	if(l>r){
		return ;
	}
	for(int i=1;i<=m;i++){
		int tmp=a[i];
		while(tmp){
			if(tmp>=mid){
				tmp-=mid;
				sum++;
			}
			else{
				tmp=0;
				sum++;
				break;
			}
		}
	}
	if(sum<=n){
		ans=min(ans,mid);
		bin(l,mid-1);
	}
	else{
		bin(mid+1,r);
	}
}
int main(){
    cin.tie(0);
    cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>a[i];
		Max=max(Max,a[i]);
	}
	bin(0,Max);
	cout<<ans;
}

加了cin.tie(0) +开O2就A了

2023/7/24 19:40
加载中...