连提问都不会?!
题目链接:
http://noi.
如果这是你的机密,起码也要以
文字形式将题目
贴完整:
1.11编程基础之二分查找
01:查找最接近的元素
总时间限制:
1000ms
内存限制:
65536kB
描述
在一个非降序列中,查找与给定值最接近的元素。
输入
第一行包含一个整数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
程序代码:
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;
int main( void )
{
vector<unsigned> buf;
{
size_t n;
cin >> n;
buf.resize( n );
copy_n( istream_iterator<unsigned>(cin), n, buf.begin() );
}
vector<unsigned> query;
{
size_t n;
cin >> n;
query.resize( n );
copy_n( istream_iterator<unsigned>(cin), n, query.begin() );
}
for( const auto& q : query )
{
auto itor = lower_bound( buf.begin(), buf.end(), q );
if( itor == buf.begin() )
cout << buf.front() << '\n';
else if( itor == buf.end() )
cout << buf.back() << '\n';
else if( (*itor-q) < (q-*std::prev(itor)) )
cout << *itor << '\n';
else
cout << *std::prev(itor) << '\n';
}
}