Java教程

二分练习

本文主要是介绍二分练习,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

二分练习

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

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

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

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

思路: 比起一般的二分,更难一些。如果没找到要找的数,就要输出距离最近的数。所以需要处理左右两边的数,还要处理边界的问题。用二分找出来的数,要与你要找的数,进行对比,一样就输出这个数。
不一样,就看你二分出来的数(这里如果我没找到的话,我选择的是比要找的数小的最大的数,那它右边就是比要找的数大的数,记作left,right)left和right和目标数看谁更接近,就输出谁,一样的话,就都输出。
代码放在下面。思路已写,注释略写。(主要还是我要记笔记,和练习自己的二分能力)

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=10000010;
int a[N];
int ex_find(int l,int r,int k) { //二分
    int mid;
    while(l<=r) {
        mid=(l+r)/2;
        if(a[mid]==k) return mid;
        else if(a[mid]>k) r=mid-1;
        else if(a[mid]<k) l=mid+1;
    }
    if(a[mid]<=k) return mid;
    else return mid-1;
}

int main() {
    int n,m;
    while(~scanf("%d%d",&n,&m)) {
        for(int i=0;i<n;i++) scanf("%d",&a[i]);
        sort(a,a+n);
        while(m--) {
            int k;
            scanf("%d",&k);
            if(k>=a[n-1]) {  //处理边界,找的数比最大的数还大就直接输出最大的数
                printf("%d\n",a[n-1]);
                continue;
            }
            else if(k<=a[0]) { //同上
                printf("%d\n",a[0]);
                continue;
            }
            int now=ex_find(0,n-1,k);  //下面写的就与思路一样了
            if(a[now]==k) {
                printf("%d\n",a[now]);
            }
            else {
                if(k-a[now]==a[now+1]-k) {
                    printf("%d %d\n",a[now],a[now+1]);
                }
                else if(k-a[now]<a[now+1]-k) {
                    printf("%d\n",a[now]);
                }
                else if(k-a[now]>a[now+1]-k) {
                    printf("%d\n",a[now+1]);
                }
            }
        }
    }
    return 0;
}

To be continued
如果你有任何建议或者批评和补充,请留言指出,不胜感激

这篇关于二分练习的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!