二分查找

STL中二分查找函数：

  • lower_bound

  • upper_bound

  • binary_search

    均运用于有序区间（二分法查找的前提）

lower_bound返回第一个查找的元素位置

upper_bound返回最后一个查找到的元素的下一个位置

如果待查找的value不存在，两者均返回假设这样的元素存在时应该出现的位置。

binary_search查找到返回true，不存在返回false

需要包含头文件algorithm

eg：

1 2 2 3 4 4 4 4 5 6 7 9 9 10

first last

lower_bound(first,last,4)—>返回3

upper_bound(first,last,4)—>返回8

Home_ _W的猜数字游戏

Problem Description：

Home. W有n个数字组成的数列,且后一个数字严格大于前一 个( a[i+1]>a[i])

V. _Dragon进行Q次猜数,每次他都猜一个x ,若这个x在数列中, V_Dragon的得分加上这个数的大小(注:被猜中的数不会从数列消失)如:数列12345 6V_Dragon猜5次,分别为1 13 5 7那V_Dragon的得分为1+1+3+5=10

现在请你告诉V. _Dragon他的得分为多少

Input

第一行输入一个T (0<T<=100)

接下来T组测试数据

每组第一行两个数n,q(1<=n,q<1000000

接下来-行n个数a1,a2..an(1<=a1<=10^9)

再接下来- -行9个数b1.b2… bq (1<=b[i]<=10^9)表示猜的数字

output

输出Home_W的得分

SampleInput

1
2
3
4
1
6 5
1 2 3 4 5 6
1 1 3 5 7

SampleOutput

10

参考代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
long long t,n,m,p[1000005],q[1000005];
long long i,sum;

int main(){
	cin>>t;
	while(t--)
	{
		sum=0;
		memset(p,0,sizeof(p));
		memset(p,0,sizeof(q));
		cin>>n>>m;
		for(i=1;i<=n;i++)//数组下标从1开始避免数组越界的情况
			cin>>p[i];
		for(i=1;i<=m;i++){
			cin>>q[i];
			if(q[i]==p[lower_bound(p+1,p+n+1,q[i])-p]) sum+=q[i];//因为测试数据庞大，如果按照普通写法运行会超时
		}
		cout<<sum<<endl;
	}
	return 0;
	
}

简单的询问

描述

这天，A君刚打完周赛。由于打得不错，他趟在椅子上悠闲的把玩这一一个长度为n的数列C . 丝毫没有刷题的意思。这时候,集训队队长B君看不下去了。他拿起A君的数列说。我有m个询问，每个询问我会说出一个整数x ， 而你需要回答整數x在数列C里面出现的次数。A君一下子僧了，他越来越院，机智的你能帮一下A君么 ?

输入

本题为单组数据评测。

第一行两个整数n ,m. n表示数列C的长度, m表示B君的询问个数( 1<=n, m<=100000 )

第二行为n个空格隔开的整数c; ,表示C数列。( -10^9≤ Ci ≤10^9 )

第三行到第m+2行,每行个整数x, 表示B君的询问。( -10^9≤ x ≤10^9 )

输出

共m行,每行一个整数y ,表示整数x在数列C里面出现的次数。

样例输入

1
2
3
4
5
5 3
9 6 3 3 2
1
3
9

样例输出

1
2
3
0
2
1

参考代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
int n,m,q,i;
long long a[100005];

int main(){
	cin>>n>>m;
	for(i=1;i<=n;i++){
		cin>>a[i];
	}
	sort(a+1,a+n+1);
	for(i=1;i<=m;i++)
	{
		cin>>q;
		int count=upper_bound(a+1,a+n+1,q)-lower_bound(a+1,a+n+1,q);//写个草稿很好理解
		cout<<count<<endl;
	}
}