P2249 【深基13.例1】查找

输入：

11 3
1 3 3 3 5 7 9 11 13 15 15
1 3 6

输出：

1 2 -1 

答案1

#include<iostream>
using namespace std;
const int N=1000010;
int n,m;
int a[N];
int find(int k)
{
	int l=1,r=n;
	while(l<r)
	{
		int mid=(l+r)/2;
		if(a[mid]>=k){
			r=mid;
		}
		else{
			l=mid+1;
		}
		
	
	}
	if(a[l]==k)return l;
		else return -1;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	
	while(m--)
	{
	   int k;
	   scanf("%d",&k);
	   printf("%d ",find(k));
		
	}
	
	return 0;
}

答案二

#include<bits/stdc++.h>
using namespace std;
int n,m,a[1000005];
int find(int x){
	int l=1,r=n;
	while(l<r){
		int mid=l+(r-l)/2;
		if(a[mid]>=x)r=mid;
		else l=mid+1;
	}
	if(a[l]==x)return l;
	else return -1;
}
int main()
{ int tmp;//临时变量 

  cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=0;i<m;i++){
        cin>>tmp;
		cout<<find(tmp)<<" "; 
	}
	
	return 0;
}

用了bower_lound函数代码

//系统函数：lower_bound(bigine指针，end指针，找的数k)：从左边让k***去是的数列的单调性不改变 
//返回下标 a+下标-a=下标 ，函数返回的是a+下标要得到下标还得减去a
#include<bits/stdc++.h>
using namespace std;
int n,m,a[1000005];

int main()
{ int tmp;//临时变量 

  cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=0;i<m;i++){
        cin>>tmp;
        int mark=lower_bound(a+1,a+n+1,tmp)-a;
		if (a[mark]==tmp)cout<<mark<<" ";
		else cout<<"-1 "; 
	}
	
	return 0;
}

P1102 A-B 数对

输入

4 1
1 1 2 3

输出

3

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=200010;
int n;
long long c,a[N];
int main(){
	scanf("%d %lld",&n,&c);
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
	sort(a+1,a+1+n);//从小到大排序
	int l=1,r=1;//[1,1]区间 
	long long ans=0; 
	for(int i=1;i<=n;i++)//遍历所有的A去找B
	{
		if (a[i]<c)continue;//a[i]本身小于c的就跳过
		 while(a[i]-c>a[l])l++;//左指针右移移动到第一个可能的数
		  if(a[i]-c==a[l]){//存在这样的数对 
		  	r=max(l,r);
		  	while(a[l]==a[r])r++;//[l,r) 
			  ans+=r-l;
		  } 
	 } 
	cout<<ans;
	return 0;
}

//uper_bound(begin,end,k)从后面找到那个插入数据的不改变单调性的地方 
//伪代码，找到所有的啊a[j]是的tb+c==a[j]思路，但是没用这个方法
//巧用lower_bound()和upper_bound() 
#include<bits/stdc++.h>
using namespace std;
int n,c,a[200005];
long ans=0;
int main(){
	cin>>n>>c;
	for(int i=0;i<n;i++)cin>>a[i];
	sort(a,a+n);
	for(int i=0;i<n;i++){
		ans+=upper_bound(a,a+n,a[i]+c)-lower_bound(a,a+n,a[i]+c);
	}
	cout<<ans<<endl;
	return 0;
}

P1873 [COCI 2011/2012 #5] EKO / 砍树