CCF NOI 1044.最近元素

2024-06-11 14:08

文章标签 ccf 元素最近 noi 1044

本文主要是介绍CCF NOI 1044.最近元素，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

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

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

样例输入
3
2 5 8
2
10
5

样例输出
8
5

解题思路

非降序列，可以采用二分查找，这样每次查找的复杂度可以降到log级别。
查找可能找到那个元素，也可能找不到，即使找不到，也要返回一个最接近的。因此，为了方便写代码，我们可以把他们合并在一起，即找最接近的2个元素，谁更接近就输出谁（如果找到的话，相等的更接近），这样可以避免很多细微的容易出错的地方。

代码中，find函数退出循环时，l+1等于r，l是1或者a[l]比k小，r是n或者a[r]不比k小。代码中，find函数退出循环时，l+1等于r，l是1或者a[l]比k小，r是n或者a[r]不比k小。如果k在a[1]和a[n]之间，那么a[l]<=k<=a[r]，否则a[l]<=a[r]

#include <iostream>
#include <cmath>
#include <cstdlib>
using namespace std;
int a[1000009];
int search(int l,int r,int k)
{while(l+1<r) //剩下两个来做选择{int m=(l+r)/2;   //先求中间if(a[m]<k) l=m;  //小了找右边else  r=m;     //大了找左边}if(abs(a[r]-k)<abs(a[l]-k))return a[r];elsereturn a[l];  //包含两种情况，一种是大于，一种是等于，等于的时候输出小的那个，因为l会小于r，所以输出a[l]
}int main()
{int n,m;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];cin>>m;for(int i=0;i<m;i++){int temp;cin>>temp;int ans= search(1,n,temp);cout<<ans<<endl;}return 0;
}