碰到的一般题型:1.准确值二分查找,或者三分查找(类似二次函数的模型)。
2.与计算几何相结合答案精度要求比较高的二分查找,有时与圆有关系时需要用到反三角函数利用 角度解题。
3.不好直接求解的一类计数问题,利用二分直接枚举可能的结果,再检查是否符合题目要求。
4.区间求解,即利用两次二分分别查找有序序列左右上下限,再求差算出总个数。
题型知识补充:
1.
三分的一般写法:
double thfind(double left,double right)
{
double midmid,mid;
while(left + 1e- < right)
{
mid = (left + right)/;
midmid = (mid+right)/;
if(scla(mid) < scla(midmid))
right = midmid;
else
left = mid;
}
return scla(left);
}
2.
PI = acos(-1.0);
一圈 = 2*PI;
3.
light oj 1076 Get the Containers;
4.
lower_bound(begin(),end(),stand);
upper_bounder(,,);
int Bsearch_lower_bound(int x)
{
int l = , r = n - , mid = ;
while (l <= r)
{
mid = (l + r) >> ;
if (a[mid] < x) l = mid + ;
else r = mid - ;
}
return l;
} int Bsearch_upper_bound(int x)
{
int l = , r = n - , mid = ;
while (l <= r)
{
mid = (l + r) >> ;
if (a[mid] <= x) l = mid + ;
else r = mid - ;
}
return l;
}
虽然啥都干不好,但是还是得坚持呀。