第17课作业:二分

潘CSP200八点班

2023-07-20 9:21:20
2023-07-30 9:21:20

信息与公告

STL二分查找语法:用于有序序列的查找

从下标1开始:
int p = lower_bound(a+1, a+n+1, k)-a:返回数组a中大于等于k的第一个值的下标
int p = upper_bound(a+1, a+n+1, k)-a:返回数组a中大于k的第一个值的下标
注:如果没有找到大于等于k的数,返回n+1。

整数二分模板:找到满足条件的第1个值的下标,如果没找到则输出 n (r 的初始值)

int l=0,r=n;
while(l<r)
{
	int m=(r-l)/2+l;
	if(满足条件)    	
		r=m;		
	else		
		l=m+1;		
}
cout<<l<<endl;   

实数二分模板

double l=0, r=n; 
while(l+(1e-6)<r)
{
	double mid=(l+r)/2;
	if(满足条件)
		r=mid;	
	else
		l=mid;	
}
printf("%.2f",l);
状态 题目 统计
分巧克力【蓝桥杯】 5 / 7 / 7
工资计算 4 / 5 / 6
吃雪糕 3 / 3 / 4
数列分段 II 4 / 7 / 7
蜗蜗棋 0 / 4 / 4
剪绳子 1 / 1 / 2