一、程序阅读。

#include<bits/stdc++.h>
using namespace std;
int a[1000001],b[10000000];
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1; i<=n; i++)
	{
		cin>>a[i];
	}
	for(int i=1; i<=m; i++)
	{
		cin>>b[i];
	}
	for(int i=1; i<=m; i++)
	{
		int c=b[i];
		int left=1,right=n,mid,temp=-1;
		while(left<=right)
		{
			mid=(left+right)/2;
			if(a[mid]==c)
			{
				temp=mid;
				right=mid-1;
			}
			else if(a[mid]>c)
			{
				right=mid-1;
			}
			else
			{
				left=mid+1;
			}
		}
		b[i]=temp;
	}
	for(int i=1; i<=m; i++)
	{
		cout<<b[i]<<" ";
	}
	return 0;
}

判断题

1. 第15行temp=-1,可以修改temp=0，程序结果不会发生改变。 {{ select(1) }}

• 对
• 错

2. 此程序时间复杂度O(n*log(2m))。 {{ select(2) }}

• 对
• 错

3. 程序执行到28行,left<right。 {{ select(3) }}

• 对
• 错

4. 主函数前面的int可以改成long long。 {{ select(4) }}

• 对
• 错

选择题

5. 执行程序，输入下列数据后，输出的结果为?

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

{{ select(5) }}

• 1 2 -1
• 1 3 -1
• -1 -1 -1
• 3 2 -1

二、程序填空

题目描述

给出一串正整数数列以及一个正整数C，要求计算出所有满足A−B=C 的数对的个数（不同位置的数字一样的数对算不同的数对）。

输入格式

输入共两行。

第一行，两个正整数N,C。

第二行，N 个正整数，作为要求处理的那串数

输出格式

一行，表示该串正整数中包含的满足A−B=C 的数对的个数。

输入/输出样例

4 1
1 1 2 3

3

代码如下

#include<bits/stdc++.h>
using namespace std;
long long a[1000001];
long long n,m;
int main()
{
	cin>>n>>m;
	for(int i=1; i<=n; i++)
	{
		cin>>a[i];
	}
	long long sum=0;
	sort(a+1,a+n+1);
	for(int i=1; i<=n; i++)
	{
		int d=a[i]+___①___;
		int left=1,right=n,z1=0,z2=0;
		while(left<=right)
		{
			int mid=(left+right)/2;
			if(a[mid]==d)
			{
				z1=mid;
				___②___;
			}
			else if(a[mid]>d)
			{
				right=mid-1;
			}
			else
			{
				left=mid+1;
			}
		}
		___③___;
		while(left<=right)
		{
			int mid=(left+right)/2;
			if(a[mid]==d)
			{
				z2=mid;
				left=mid+1;
			}
			else if(a[mid]>d)
			{
				right=mid-1;
			}
			else
			{
				left=mid+1;
			}
		}
		if(z1==0||___④___)
		{
			continue;
		}
		___⑤___
	}
	cout<<sum;
	return 0;
}

6. 第①处应填。 {{ select(6) }}

• a[m]
• m
• a[m-1]
• m-1

7. 第②处应填。 {{ select(7) }}

• break
• continue
• right=mid-1
• left=mid-1

8. 第③处应填。 {{ select(8) }}

• left=1
• left=1, right=n
• right=1
• left=1, riht=n-1

9. 第④处应填。 {{ select(9) }}

• z2=0
• z2==0
• z2>0
• z2<0

10. 第⑤处应填。 {{ select(10) }}

• sum=sum+(z2-z1+1)/2;
• sum=sum+(z2-z1+1);
• sum=(z2-z1+1);
• sum=sum+(z2-z1);