sincerit 吃饭啦(二分查找，lower

sincerit 吃饭啦(二分查找，lower_bound())

本文主要是介绍sincerit 吃饭啦(二分查找，lower_bound())，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链接：https://ac.nowcoder.com/acm/contest/289/F
来源：牛客网

题目描述
饿啦，该吃饭啦！一条街上好多家店呀，都没吃过，作为吃货，我一定要每家都吃一遍。就近原则，就挑一家最近的吃吧！
这条街长度为n，上面有m家店。给定q个吃货所在的位置，请告诉每个吃货离他最近的店有多远。
输入描述:
第1行含有两个正整数n和m，含义如题目中所述。
第2行含有m个以空格分割的正整数ai，表示每家店所在的坐标。
第3行含有一个正整数q，表示接下来有q个吃货所在的坐标。
第4行至第q+3行，每行内有一个正整数bi表示第i个吃货所在的坐标。
对于输入的数据，约定：
① 1≤n≤109，1≤m≤min(n,103)，1≤q≤105。
② 对于任意的1≤i≤m，有1≤ai≤n。
③ 不会有多家店在同一坐标上，即当1≤i,j≤n且i≠j时，有ai≠aj。
④ 对于任意的1≤i≤q，有1≤bi≤n。
输出描述:
对于输入的每一个吃货所在的位置，请输出一行，该行内仅有一整数，表示他离与他最近的店的距离。
示例1
输入
复制
3 1
1
3
1
2
3
输出
复制
0
1
2

可以二分查找找到比吃货所在的位置大的第一个店的坐标
同样可以用lower_bound函数去查找

#include <stdio.h>
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
vector<int> v;
int main() {int n, m, x, q, u;scanf("%d%d", &n, &m);for (int i = 0; i < m; i++) {scanf("%d", &x);v.push_back(x);}sort(v.begin(), v.end());scanf("%d", &q);while (q--) {scanf("%d", &u);int pos = lower_bound(v.begin(), v.end(), u) - v.begin(); // 查找大于或等于u的第一个元素位置if (pos == v.size()) printf("%d\n", u - v[pos-1]);  // 返回了长度说明没找到else if (pos == 0) printf("%d\n", v[pos]-u);else printf("%d\n", v[pos]-u > u-v[pos-1] ? u-v[pos-1]:v[pos]-u);}return 0;
}