ZOJ 2029 The Intervals (二分查找)

于 2011年03月20日 发布在 算法&&ACM 跳到评论

ZOJ 2029 The Intervals

给出数组a,求的最小的一个[ a[i], a[j] )使得b[m]在这个区间内,简单的方法就是排序,然后查找范围。为了练习二分,我学习了lower_bound和upper_bound,哈哈stl好强大,以后做题时不能因为不会用二分而超时了。lower_bound(a.begin(),b.end(),x)返回一个迭代器,使得这个位置的元素>=x,用upper_bound则表示>x


#include<iostream>
#include<string>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<cstdio>
#define M 30
using namespace std;

int main(void)
{
    int n,m,x;
    while( cin >> n >> m )
    {
        vector<int> a;
        for( int i = 0; i < n; i++ ){
            cin >> x;
            a.push_back(x);
        }
        sort( a.begin() ,a.end() );
        while( m-- )
        {
            cin >> x;
            vector<int>::iterator start,end;
            start = lower_bound(a.begin(),a.end(),x);
            end   = upper_bound(a.begin(),a.end(),x);
            if( end == a.end() )
                cout << "no such interval" << endl;
            else if( start == a.begin() && *start != x )
                cout << "no such interval" << endl;
            else{
                if( *start != x ) start--;
                cout << '[' << *start << ',' << *end << ')' << endl;
            }
        }
        cout << endl;
    }
    return 0;
}

本文共有 一条评论 | 沙发:文章评论

  1. 小媛说道:

    不会用STL啊 不会用。。。姐,你下面没有哭的那个很可爱的表情。。。 :arrow:

留下评论!

:wink: :twisted: :roll: :oops: :mrgreen: :lol: :idea: :evil: :cry: :arrow: :?: :-| :-x :-o :-P :-D :-? :) :( :!: 8-O 8)