| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1224 人关注过本帖
标题:求助!这题我自己搞不定了
只看楼主 加入收藏
根根本根
Rank: 2
来 自:上海
等 级:论坛游民
帖 子:64
专家分:15
注 册:2018-3-19
结帖率:62.5%
收藏
已结贴  问题点数: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++ 
2018-10-18 20:22
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9024
专家分:54030
注 册:2011-1-18
收藏
得分: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';
    }
}


2018-10-19 09:50
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9024
专家分:54030
注 册:2011-1-18
收藏
得分: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) );
    }
}


2018-10-19 10:26
快速回复:求助!这题我自己搞不定了
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.051181 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved