二分练习
Time Limit: 1000MS Memory limit: 65536K
题目描述
给你一个序列，然后给你m个元素，让你从序列中找出与每个元素最接近的数字输出来，如果有两个就输出两个。
输入
多组输入，第一行给你两个数n（0 < n < 10000000）,m(0 < m < n),接下来是数列的n个数，然后再输入m个元素，让你找出最接近每个元素的值。如果有两个，按从小到大输出。
输出
这m个数分别输出最接近每个元素的值，组与组之间输出一个空行。
示例输入
8 4 1 2 3 4 5 6 8 11 4 9 2 7
示例输出
4 8 2 6 8
提示
来源
lwn
示例程序
WA了好多次，终于对了，这陷阱好不给力啊
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
int main()
{
int n,a[100010],i,a1,m,m1,l,v,j;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i=0;i<n;i++)
{scanf("%d",&a[i]);
}
sort(a,a+n);
for(i=0;i<m;i++)
{
scanf("%d",&a1);
if(upper_bound(a,a+n,a1)-lower_bound(a,a+n,a1))
{
printf("%d\n",a1);
}
else
{
m1=n-1;//终点
v=0;//起点
while(m1-v>1)
{
l=(m1+v)/2;
if(a[l]>a1)m1=l;
else v=l;
}
if(fabs(a[m1]-a1)>fabs(a[v]-a1))
{printf("%d\n",a[v]);}
else if(fabs(a[m1]-a1)<fabs(a[v]-a1))
{printf("%d\n",a[m1]);}
else if(a[m1]-a1+a[v]-a1==0){printf("%d %d\n",a[v],a[m1]);}
else printf("%d\n",a[m1]);
}
}
printf("\n");
}
}
利用上下界函数
#include<stdio.h>
#include<algorithm>
using namespace std;
int upper(int a[], int n, int x)
{
int lo = 0, hi = n - 1, mid;
while (lo < hi)
{
mid = (lo + hi + 1) / 2;
if (a[mid] <= x)
lo = mid;
else
hi = mid - 1;
}
return lo;
}
int lower(int a[], int n, int x)
{
int lo = 0, hi = n - 1, mid;
while (lo < hi)
{
mid = (lo + hi) / 2;
if (a[mid] >= x)
hi = mid;
else
lo = mid + 1;
}
return lo;
}
int main()
{
int n,m,i,l1,l2,key,x[10001111];
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i=0;i<n;i++)
scanf("%d",&x[i]);
sort(x,x+n);
while(m--)
{
scanf("%d",&key);
l1=upper(x,n,key);
l2=lower(x,n,key);
//printf("%d %d\n",x[l1],x[l2]);
if(x[l1]==x[l2])printf("%d\n",x[l1]);
else
{
if((key-x[l1])==(x[l2]-key))
printf("%d %d\n",x[l1],x[l2]);
else if((key-x[l1])<(x[l2]-key))
printf("%d\n",x[l1]);
else printf("%d\n",x[l2]);
}
}printf("\n");
}
return 0;
}