NC20865. 救救兔子
描述
某天，一只可爱的小兔砸在路上蹦蹦跳跳地走着，怪人PM6出现了，于是小兔子被盯上了。
PM6：“免子。哦不，小兔子。你长得真好…不对，真可爱。我这里有一道很容易很容易的题目，答对了我就请你吃萝卜，答错了你就请我吃兔肉，好不好呀~~？”
小兔砸：“萝卜！？好呀好呀好呀。”于是笨笨的兔纸入套了。
PM6：“我这里有一个由 N 个数组成的序列，给你 M 个询问，每个询问会给你一个数 X ，对于每个询问，你要回答出序列中与这个值最接近的元素。”
听完题后，兔子吓成一坨免子了，面临着变成红烧兔头的危险，求求你救救兔子！
输入描述
第一行包含一个整数N，为序列长度。
第二行包含N个整数，为序列各元素。
第三行包含一个整数M，为PM6的询问个数。
接下来M行，每行一个整数X，为要询问最接近元素的给定值。
对于40%的数据：1<=N<=10000，1<=M<=1000
对于另外10%的数据：M=1
对于100%的数据：1 <=N<= 100000，1<=M<=10000，0<=序列中的每个数，X<=1e9
输出描述
M行，每行有一个整数，为最接近相应给定值的元素值，保持输入顺序。若有多个值满足条件，输出最小的一个。
示例1
输入:
5 2 4 5 5 7 3 2 5 6
输出:
2 5 5
C++14(g++5.4) 解法, 执行用时: 23ms, 内存消耗: 608K, 提交时间: 2019-04-03 18:32:49
#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[200000];
int main(){
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
}
sort(a,a+n);
cin>>m;
for(int i=0;i<m;i++){
int x;
cin>>x;
int y=lower_bound(a,a+n,x)-a;
if(abs(a[y]-x)>=abs(a[y-1]-x)){
cout<<a[y-1]<<endl;
}
else cout<<a[y]<<endl;
}
}
C++(clang++11) 解法, 执行用时: 118ms, 内存消耗: 560K, 提交时间: 2020-10-31 21:53:36
#include<bits/stdc++.h>
using namespace std;
long i,n,x,a[100001],m,M,t;
int main()
{
cin>>n;
for(;i<n;i++)cin>>a[i];
sort(a,a+n);
for(cin>>m;m--;)
{
cin>>x;M=2e9;
for(i=0;i<n;i++)
if(abs(a[i]-x)<M)
M=abs(a[i]-x),t=a[i];
cout<<t<<endl;
}
}