题解:openjudge 1.11——01

题目

分享图片

 思路:二分查找

来,上代码

 

分享图片
#include<cstdio>
#include<iostream>
using namespace std;
int a[100000+100];
int n,m;
int find(int x){
    int l,r;
    l=0;r=n-1;
    while(l<r){
        int mid=(l+r)/2;
        if(a[mid]>=x) r=mid;//找离x最近的那个最小的数 
        else l=mid+1;
    }
    if (l==0) return 0;    //如果找的值是所有数中的最小值,则直接返回最小下标0。
    return x-a[l-1]<=a[l]-x?l-1:l;//循环结束时l=r, 此时a[l]>=x,a[l-1]<x,从两者中找出一个符合题意的 
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    cin>>m;
    for(int i=0;i<m;i++){
        int x,p;
        cin>>x;
        p=find(x);
        cout<<a[p]<<endl;
    }
    return 0;
}
View Code
相关文章
相关标签/搜索