#K4004. C4.04 二分查找
C4.04 二分查找
一、程序阅读。
#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;
}
判断题
- 第15行temp=-1,可以修改temp=0,程序结果不会发生改变。 {{ select(1) }}
- 对
- 错
- 此程序时间复杂度O(n*log(2m))。 {{ select(2) }}
- 对
- 错
- 程序执行到28行,left<right。 {{ select(3) }}
- 对
- 错
- 主函数前面的int可以改成long long。 {{ select(4) }}
- 对
- 错
选择题
- 执行程序,输入下列数据后,输出的结果为?
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;
}
- 第①处应填。 {{ select(6) }}
- a[m]
- m
- a[m-1]
- m-1
- 第②处应填。 {{ select(7) }}
- break
- continue
- right=mid-1
- left=mid-1
- 第③处应填。 {{ select(8) }}
- left=1
- left=1, right=n
- right=1
- left=1, riht=n-1
- 第④处应填。 {{ select(9) }}
- z2=0
- z2==0
- z2>0
- z2<0
- 第⑤处应填。 {{ select(10) }}
- sum=sum+(z2-z1+1)/2;
- sum=sum+(z2-z1+1);
- sum=(z2-z1+1);
- sum=sum+(z2-z1);