2866: 练56.2 查找最接近的元素

内存限制：64 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：1 解决：1

题目描述

在一个非降序列中，查找与给定值最接近的元素。

输入

第一行包含一个整数$n$，为非降序列长度。$1≤n≤100000$。
第二行包含$n$个整数，为非降序列各元素。所有元素的大小均在$0\sim 1,000,000,000$之间。第三行包含一个整数$m$，为要询问的给定值个数。$1≤m ≤10000$。
接下来$m$行，每行一个整数，为要询问最接近元素的给定值。所有给定值的大小均在$0\sim 1,000,000,000$之间。

输出

$m$ 行，每行一个整数，为最接近相应给定值的元素值，保持输入顺序。若有多个值满足条件，输出最小的一个。

样例输入 复制 

3
2 5 8
2
10
5

样例输出 复制 

8
5

提示

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=1e5+10;
int n,m,b;
int a[maxn];
int main(){
    scanf("%d",&n);
    for (int i=0;i<n;++i){
        scanf("%d",&a[i]);
    }
    scanf("%d",&m);
    for (int i=0; i<m;++i){
        scanf("%d",&b);
        if (b>a[n-1]) {
            printf("%d\n",a[n-1]);
            continue;
        }
        if (b<=a[0]) {
            printf("%d\n",a[0]);
            continue;
        }
        int x=lower_bound(a,a+n,b)-a;
        if (a[x]-b<b-a[x-1]) {
            printf("%d\n",a[x]);
        }
        else {
            printf("%d\n",a[x-1]);
        }
    }
    return 0;
}

来源/分类

提交提交记录统计露一手!