二分练习

Time Limit: 1000MS Memory Limit: 65536KB

Problem Description

给你一个序列，然后给你m个元素，让你从序列中找出与每个元素最接近的数字输出来，如果有两个就输出两个。
 

Input

 多组输入，第一行给你两个数n（0 < n < 10000000）,m(0 < m < n),接下来是数列的n个数，然后再输入m个元素，让你找出最接近每个元素的值。如果有两个，按从小到大输出。
 

Output

 这m个数分别输出最接近每个元素的值，组与组之间输出一个空行。

Example Input

8 4
1 2 3 4 5 6 8 11
4
9
2
7

Example Output

4
8
2
6 8

Hint

 

Author

lwn

本题坑点，1要先进行排序2当查到数据在原集合中有多个（即该数据与集合中的数据相等）时，只输出一个
3.先处理边界情况 4.按查到查不到进行分类 
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main()
{
    vector<int>o;
    int n;
    while(cin>>n)
    {
        int m;
        cin>>m;
        o.clear();
        for(int i=1; i<=n; i++)
        {
            int num;
            scanf("%d",&num);
            o.push_back(num);
        }
        sort(o.begin(),o.end());
        while(m--)
        {
            int u;
            scanf("%d",&u);
            int y = lower_bound(o.begin(),o.end(),u)-o.begin();
            //先查到比其大的第一个数的位置
            //处理边界情况
            if(y>=n)
            {
                cout<<o[n-1]<<endl;
                continue;
            }
            else if(y==0)
            {
                cout<<o[0]<<endl;
                continue;
            }
            //比较查不到时左右两个值的差
            if(o[y]!=u)
            {
                int d1,d2;
                d1 = u - o[y-1];
                d2 = o[y] - u;
                if(d1==d2)
                    cout<<o[y-1]<<" "<<o[y]<<endl;
                else if(d1<d2)
                    cout<<o[y-1]<<endl;
                else
                    cout<<o[y]<<endl;
            }
            else
            {
                //数据中有与待查询的数多个时，只输出1个；
                /*if(y-1>=0&&o[y-1]==u)
                cout<<u<<" "<<u<<endl;
                else if(y+1<n&&o[y+1]==u)
                  cout<<u<<" "<<u<<endl;
                else*/
                cout<<u<<endl;

            }
        }
        printf("\n");

    }
    return 0;
}