求助！这题我自己搞不定了 - C++教室 - C++论坛

已结贴√ 问题点数：6 回复次数：2

求助！这题我自己搞不定了

图片附件: 游客没有浏览图片的权限，请登录或注册

#include <bits/stdc++.h>
using namespace std;
long a[1000]={0};
int halfind(long x,int lbound,int rbound){
    int rank=lbound+ceil((rbound-lbound)/2);
    if(rbound==lbound){
        return a[lbound];
    }
    if(x>a[rank]){
        return halfind(x,rank,rbound);
    }
    else if(x<=a[rank]){
        return halfind(x,lbound,rank);
    }
}
int main(){
    int n,m;
    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 t;
        cin>>t;
        cout<<halfind(t,0,n-1)<<endl;
    }
    return 0;
}

图片附件: 游客没有浏览图片的权限，请登录或注册

搜索更多相关主题的帖子: int　rank　return　cin　i++　

第 2 楼

得分:6

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

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

第 3 楼

得分:0

不用算法库，全部自己写

程序代码：

#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) );
    }
}