AKSZ-二分算法

「仆人」阿蕾奇诺

2024-03-31 17:35:38

发布于：广东

5阅读

0回复

0点赞

二分

文件判题：

输入文件：
（输入）文件名：
(输入文件名，不一定是data.in)

freopen("data.in","r",stdin)

输出文件：

freopen("data.out","w",stdout)

fclose(stdin)
fclose(stdout)

加快cin

取消压栈

inline int read(){
	int x = 0,f = 1;char ch = getchar();
	while(ch<'0'||ch>'9'){
		if(ch == '-'){
			f = -1;
		}
		ch = getchar();
	}
	while(ch>='0'&&ch<='9'){
		x = x*10+ch-'0';
		ch = getchar();
	}
	return x*f;
}

使用：

n = read();

普通方法：

ios::sync_with_stdio(0);
	cin.tie(0);

生成随机数

工具->编译选项->第一个空输入**-std=c++11**并勾选

mt19937 rnd(time(NULL));
	int x = 1+rnd()%10//范围;
	cout<<x;

想到思路后：
1.只能敲暴力
2.先敲正解，调试过样例，文件过大样例
3.写暴力对拍，生成随机测试数据，有错改错
4.检查是否写上freopen();

二分模板：

int l = 1,r = n;//二分上下边界
//在[l,r]闭区间 //开区间[l,r)不包括最后一个节点 
int ans = -1;
while(l<=r){
	int mid = (l+r)>>1;
	
	if(a[mid]>x){
		ans = mid;
		r = mid-1;
	}else{
		l = mid+1;
	}
} 
cout<<ans;

lower_bound(数组开头下标，数组结尾下标+1，待查元素)-数组第0个下标开头;、
返回值是第一个大于等于待查元素的下标

upper_bound(数组开头下标，数组结尾下标+1，待查元素)-数组第0个下标开头;
返回值是第一个大于待查元素的下标

用法：int id = lower_bound();

二分小数模板

double l = 0.0,r = n;//二分上下边界
	//在[l,r]闭区间 //开区间[l,r)不包括最后一个节点 
	double ans = -1;
	double eps = 1e-6;
	while(r-l>=eps){
		double mid = (l+r)/2.0;
		
		if(mid*mid<=n){
			ans = mid;
			l = mid;
			
			
			
		}else{
			r = mid;
		}
	} 
	cout<<ans;