欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

牛客二分

程序员文章站 2024-03-17 15:05:10
...

链接:https://ac.nowcoder.com/acm/contest/372/B
来源:牛客网
 

某天,一只可爱的小兔砸在路上蹦蹦跳跳地走着,怪人PM6出现了,于是小兔子被盯上了。

PM6:“免子。哦不,小兔子。你长得真好…不对,真可爱。我这里有一道很容易很容易的题目,答对了我就请你吃萝卜,答错了你就请我吃兔肉,好不好呀~~?”

小兔砸:“萝卜!?好呀好呀好呀。”于是笨笨的兔纸入套了。

PM6:“我这里有一个由 N 个数组成的序列,给你 M 个询问,每个询问会给你一个数 X ,对于每个询问,你要回答出序列中与这个值最接近的元素。”

听完题后,兔子吓成一坨免子了,面临着变成红烧兔头的危险,求求你救救兔子!

输入描述:

第一行包含一个整数N,为序列长度。
第二行包含N个整数,为序列各元素。
第三行包含一个整数M,为PM6的询问个数。
接下来M行,每行一个整数X,为要询问最接近元素的给定值。
对于40%的数据:1<=N<=10000,1<=M<=1000
对于另外10%的数据:M=1
对于100%的数据:1 <=N<= 100000,1<=M<=10000,0<=序列中的每个数,X<=1e9

输出描述:

M行,每行有一个整数,为最接近相应给定值的元素值,保持输入顺序。若有多个值满足条件,输出最小的一个。

示例1

输入

复制

5
2 4 5 5 7
3
2
5
6

输出

复制

2
5
5

代码:

#include<bits/stdc++.h>
using namespace std;
int a[100009];
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    sort(a,a+n);
    int m;
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        int x;
        cin>>x;
        int l=0;int r=n-1;
        int flag=0;
        while((r-l)>1)
        {
            int mid=(l+r)/2;
            if(a[mid]>x)
            {
                r=mid;
            }
            if(a[mid]<x)
            {
                l=mid;
            }
            if(a[mid]==x)
            {
                flag=1;
                break;
            }
        }
        if(flag==1)
        {
            cout<<x<<endl;
        }
        else
        {
            if(x-a[l]<=a[r]-x)
            {
                cout<<a[l]<<endl;
            }
            else
            {
                cout<<a[r]<<endl;
            }
        }
    }
}