第九个点TLE (开O2AC 但考试无法O2)
查看原帖
第九个点TLE (开O2AC 但考试无法O2)
540177
wyf_sinon楼主2022/6/9 20:43

蒟蒻二分TLE求助二分只知道思路具体条件总是添不来 二分TLE我觉得是我思路有问题 我就是每次烘干完再降序排序 以下为二分代码

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int n,a,b,k,temp;
int wet[500010];
bool cmp(int x,int y){
	return x>y;
}
int main(){
	scanf("%d %d %d",&n,&a,&b);
	b=a+b;
	for(int i=1;i<=n;i++){
		scanf("%d",&wet[i]);
	}
	sort(wet+1,wet+1+n,cmp); //降序
	while(wet[1]>0){ //降序的话 头小于0就结束
    //烘干
		int x=wet[1]-b;
		for(int i=2;i<=n;i++){
			wet[i]-=a;
		}
     //我的垃圾二分   
		int l=1,r=n,ans;
		while(l<=r){ 
			int mid=(l+r)/2;
			if(x>wet[mid]){
				r=mid-1;
			}else if(x<wet[mid]&&x<wet[mid+1]){
				l=mid+1;
			}else if(x<=wet[mid]&&x>=wet[mid+1]){
				ans=mid;
				break;
			}
		}
     //重新排序
		for(int i=1;i<ans;i++){
			wet[i]=wet[i+1];
		}
		wet[ans]=x;
		temp++;
		while(wet[n]<=0) n--;//已经干的就不看了
	}
	printf("%d",temp);
	return 0;
}

求救 我想不到更优的方法了

2022/6/9 20:43
加载中...