二分练习
Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^_^
题目描述
给你一个序列，然后给你m个元素，让你从序列中找出与每个元素最接近的数字输出来，如果有两个就输出两个。
输入
多组输入，第一行给你两个数n（0 < n < 10000000）,m(0 < m < n),接下来是数列的n个数，然后再输入m个元素，让你找出最接近每个元素的值。如果有两个，按从小到大输出。
输出
这m个数分别输出最接近每个元素的值，组与组之间输出一个空行。
示例输入
示例输出
#include <stdio.h>
int a[100000010];void qsort(int *a,int star ,int fin)//快排函数{ int key=a[star],i=star,j=fin; if(star>=fin) return; while(i<j) { while(i<j&&a[j]>=key) j--; a[i]=a[j]; while(i<j&&a[i]<=key) i++; a[j]=a[i]; } a[i]=key; qsort(a,star,i-1); qsort(a,i+1,fin);}int down(int *a,int low,int high,int key)//寻找key的前一个数{ int mid; int r=-1; while(low<=high) { mid=(low+high)/2; if(a[mid]<=key) { low=mid+1; r=mid; } else high=mid-1; } return r;}int up(int *a,int low,int high,int key )//寻找key的后一个数{ int mid; int r=-1; while(low<=high) { mid=(low+high)/2; if(a[mid]>=key) { r=mid; high=mid-1; } else low=mid+1; } return r;}int main(){ int n,m,i,k; while(~scanf("%d %d",&n,&m)) { for(i=0; i<n; i++) scanf("%d",&a[i]); qsort(a,0,n-1); for(i=0; i<m; i++) { scanf("%d",&k); int kmax=up(a,0,n-1,k); int kmin=down(a,0,n-1,k); if(kmax==-1)//若不存在比key大的，输出比key小的 printf("%d\n",a[kmin]); else if(kmin==-1)//若不存在比key小的，输出比key大的 printf("%d\n",a[kmax]); else if(a[kmax]==a[kmin]) printf("%d\n",a[kmin]); else { if((a[kmax]-k)==(k-a[kmin])) printf("%d %d\n",a[kmin],a[kmax]); else if((a[kmax]-k)>(k-a[kmin])) printf("%d\n",a[kmin]); else printf("%d\n",a[kmax]); } } printf("\n"); } return 0;}