求助！这题我自己搞不定了 - 编程论坛

rjsp2018-10-19 09:50

连提问都不会？！
题目链接：

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';
    }
}

rjsp2018-10-19 10:26

不用算法库，全部自己写

程序代码：

#include <cstdio>

unsigned foo( const unsigned buf[], size_t n, unsigned val )
{
    const unsigned* p = buf;
    for( size_t count=n; count!=0; )
    {
        if( *(p+count/2) < val )
            p+=count/2+1, count-=count/2+1;
        else
            count = count/2;
    }

    if( p == buf )
        return buf[0];
    if( p == buf+n )
        return buf[n-1];
    if( *p-val < val-p[-1] )
        return *p;
    return p[-1];
}

int main( void )
{
    size_t n;
    unsigned buf[100000];
    scanf( "%zu", &n );
    for( size_t i=0; i!=n; ++i )
        scanf( "%u", buf+i );

    size_t m;
    scanf( "%zu", &m );
    for( size_t i=0; i!=m; ++i )
    {
        unsigned val;
        scanf( "%u", &val );
        printf( "%u\n", foo(buf,n,val) );
    }
}