題目描述

在一個非降序列中，查找與給定值最接近的元素。

輸入

第一行包含一個整數(shù)n，為非降序列長度。1 <= n <= 100000。
第二行包含n個整數(shù)，為非降序列各元素。所有元素的大小均在0-1,000,000,000之間。
第三行包含一個整數(shù)m，為要詢問的給定值個數(shù)。1 <= m <= 10000。
接下來m行，每行一個整數(shù)，為要詢問最接近元素的給定值。所有給定值的大小均在0-1,000,000,000之間。

輸出

m行，每行一個整數(shù)，為最接近相應(yīng)給定值的元素值，保持輸入順序。若有多個值滿足條件，輸出最小的一個。

樣例輸入

3 2 5 8 2 10 5

樣例輸出

8 5

數(shù)據(jù)范圍限制

1 <= n <= 100000。

AC代碼：

#include <iostream> #include <cmath> using namespace std;long long a[100010];long long Binsearch(int left,int right,long long k) {int mid=(left+right)/2;if(a[mid]==k)return k;else if(a[mid-1]<k && a[mid]>k){if(k-a[mid-1] <= a[mid]-k)return a[mid-1];else return a[mid];}else if(a[mid]<k && a[mid+1]>k){if(k-a[mid] <= a[mid+1]-k)return a[mid];else return a[mid+1];}else if(a[mid]>k)Binsearch(left,mid,k);else if(a[mid]<k)Binsearch(mid,right,k); } int main() {int n,m;long long bs;while(cin>>n){for(int i=1;i<=n;i++)cin>>a[i];cin>>m;while(m--){cin>>bs;if(bs>=a[n])cout<<a[n]<<endl;else if(bs<=a[1])cout<<a[1]<<endl;else cout<<Binsearch(1,n,bs)<<endl;}}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的最近元素的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。