lower_bound/upper_bound使用方法

lower_bound/upper_bound使用方法

设要查找的序列为增序

lower_bound的作用是二分查找求下界，即在前闭后开区间【first，last）中查找值value，返回等于或大于value的第一个位置，若所有元素都小于value，则返回last

upper_bound的作用是二分查找求上界，即在前闭后开区间【first，last）中查找值value，返回大于value的第一个位置，若所有元素都小于value，则返回last

两个函数拥有相同的参数列表：

（区间起始位置first， 区间结束位置last， 要查找的值value）//一定要注意区间是前闭后开！！！

对于返回值要注意：

返回值是位置不假，但一般不能直接拿来用。实际上对于普通数组函数返回值为指针，对于STL里的一些容器返回值为迭代器，因此想要得到数组下标只需要把返回值和起始位置fisrt做差即可，举例：

int pos = lower_bound(a, a + n, value) - a;

然后看一下他们的应用：

Uva 1152 和为0的4个值 ​​+ b【】的值的相反数，用y【】记录所有c【】 + d【】的值，然后对对于每一个x，在y【】中二分查找进行判断

现在问题来了，如果一个x在y【】中有多个映射，根据题目要求应该都进行统计，但是普通的二分查找只能统计一次，这样的话结果必然会出错

现在两个函数就起作用了，x在y【】中的所有映射就是x在y【】中的上界减去x在y【】中的下界，调用这两个函数做差就可以完美避免这个问题了

这里要保证y【】是增序，快排即可

#include #include #include #include using namespace std;const int maxn = 4000 + 10;int n;int a[maxn], b[maxn], c[maxn], d[maxn];int x, y[maxn * maxn];void solve() { int cnt = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { y[cnt++] = c[i] + d[j]; } } sort(y, y + cnt); int ans = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { x = -(a[i] + b[j]); ans += upper_bound(y, y + cnt, x) - lower_bound(y, y + cnt, x); } } printf("%d\n", ans);}int main(){ int T, flag = 0; cin >> T; while (T--) { cin >> n; for (int i = 0; i < n; i++) { cin >> a[i] >> b[i] >> c[i] >> d[i]; } if (flag++) printf("\n"); solve(); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。