采购礼品 二分查找 算法 什么是二分查找 lower_bound()函数
题目背景
编程俱乐部为了准备开学的社团活动,需要采购活动物品,mxj联系某条街上的n个人,该条街长度为L,一共有m家店。
题目描述
现在这n个人想知道距离自己最近的店距离是多少,请你求出来。
输入输出格式
输入格式:
第一行,两个空格隔开的正整数,L, m, 题意如上。
接下来m行,每行一个正整数,表示店铺位置。
第m+1行,一个正整数n,代表人数。
接下来n行,每行一个正整数,代表第i个人所处的位置Pi。
输出格式:
输出n行,代表每个人距离自己最近店的路程。
输入输出样例
输入样例#1:
3 1
1
3
1
2
3
输出样例#1:
0
1
2
说明
1≤L≤109
1≤m≤105
1≤n≤105
且m ≤ n
参考代码1:
#include
using namespace std;
#define pb push_back
int n,l,m,a;
int M[100005];
int main(void)
{cin>>l>>m;for(int i=0;i>M[i];sort(M,M+m); //先排序cin>>n;for(int i=0;i>a;int pos=lower_bound(M,M+m,a)-M; //求第一个大于等于所处位置的商店的下标if(pos==m) //pos==m代表返回的是end,即为m,不存在cout<
参考代码2:
#include
using namespace std;
int M[100005]={0};
struct stu
{int x;//序号int y;//人的位置
}N[100005];
bool cmpren(stu a,stu b)
{return a.y>l>>m;for(int i=1;i<=m;i++)cin>>M[i];sort(M+1,M+1+m);cin>>n;for(int i=1;i<=n;i++){cin>>N[i].y;N[i].x=i;//序号}sort(N+1,N+1+n,cmpren);for(int i=1;i<=n;i++){if(N[i].y<=M[1])//全在左边N[i].y=M[1]-N[i].y;else if(N[i].y>=M[m])//全在右边N[i].y=N[i].y-M[m];else//在中间,就寻找就行了{for(j=k;j<=m;j++){if(N[i].y>=M[j]&&N[i].y<=M[j+1]){k=j;//更新kN[i].y=min(N[i].y-M[j],M[j+1]-N[i].y);//N[i].y直接就是结果了break;}}}}sort(N+1,N+1+n,cmpxu);//再按照序号排回来for(int i=1;i<=n;i++)printf("%d\n",N[i].y);return 0;
}
二分查找:
实例:
此题目: