20220253 - STL的二分查找函数

有n个以原点为圆心的圆形，其半径分别为r_i。

有q条以原点为端点的线段，其另一个端点的坐标为x_i,y_i。

每条线段与几个圆相交？

第一行，n,q。

接下来n行，每行一个r_i。

接下来q行，每行两个整数，分别表示x_i,y_i。

对于100%的数据：

1 \le n,q \le 10^6 ；

1 \le r_i,x_i,y_i \le 10^9 。

每组询问一个整数，表示该线段与几个圆相交。

这个问题的本质是给出n个可能有重复的数据，查找第一个大于v的数据是第几个。

在STL中：

lower_bound() 返回值>=给定元素的第一个位置

upper_bound() 返回值>给定元素的第一个位置

注意：其查找范围必须内必须是已排序的（函数本质是二分查找）

其语法如下：

//查找[first, last)区域中第一个大于 val 的元素。
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,
                             const T& val);
//查找[first, last)区域中第一个不符合 comp 规则的元素
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,
                             const T& val, Compare comp);

其中，first 和 last 都为正向迭代器，[first, last) 用于指定该函数的作用范围；val 用于执行目标值；comp 作用自定义查找规则，此参数可接收一个包含 2 个形参（第一个形参值始终为 val）且返回值为 bool 类型的函数，可以是普通函数，也可以是函数对象。

对于vector,set等值容器，其比较内容为实际值。

对迭代器做减法则可以求出两个迭代器之间的元素个数。例如：

//如下语句在vector<long long>vc的全部元素中查找第一个大于v的迭代器
auto p=upper_bound(vc.begin(),vc.end(),v);
//用第一个大于v的迭代器减开始的迭代器得到两者之间元素个数
cout<<(long long)(p-vc.begin())<<"\n";

//如下语句在数组long long vc[]的前vcp个元素中查找第一个大于v的迭代器
auto p=upper_bound(vc,vc+vcp,v);
//用第一个大于v的迭代器减开始的迭代器得到两者之间元素个数（数组名就是数组的第一个元素地址）
printf("%lld\n",p-vc);

这两个函数在头文件中。你可以查看其实现，了解STL底层是如何实现支持泛型的二分查找函数的。其中distance函数的功能是求两个迭代器之间的元素个数。所以，上面代码中两个迭代器之间的元素个数也可以用这个函数来求。