C/C++编程五级 题库
共 7 道题
· 按题型筛选,点「查看答案」核对解析
1
单选题
适中
在长度为n的有序数组中,二分查找的最坏时间复杂度是?( )
A
O(1)
B
O(log n)
C
O(n)
D
O(n log n)
答案与解析
正确答案:B
这道题暂未补解析。
3
单选题
适中
在一个有序序列里,二分查找一个给定的键值,算法的时间复杂度是?( )
A
O(n)
B
O(1)
C
O(log n)
D
O(n log n)
答案与解析
正确答案:C
二分查找每次将查找范围缩小一半,时间复杂度为 O(log n)。
6
判断题
偏易
二分查找可以用于查找旋转数组中的元素。( )
A
对
B
错
答案与解析
正确答案:对
旋转数组(如 [4,5,6,7,0,1,2])虽然整体不是有序的,但它由两个有序部分组成,可以通过二分查找的变体来查找元素。
7
简答题
偏难
泳池
小C在一个排水系统不太好的学校上学。又是一个下雨天,学校里高低不平积了很多水。小C突发奇想:如果大雨一直下,多久以后我可以在学校里游泳呢?
学校是 N x N 的坐标方格 grid 中,每一个方格的值 grid(i,j)表示在位置 (i,j) 的高度。现在开始下雨了。当时间为 t 时,此时雨水导致方格中任意位置的水位为 t 。你可以从一个方格游向四周相邻的任意一个方格,但是前提是此时水位必须同时淹没这两个方格。假定小C的游动是不耗时的。
现在小C从坐标方格的左上(0,0)出发。最少耗时多久他才能到达坐标方格的右下平台 (N-1, N-1)?
时间限制:1000
内存限制:65536
输入
第一行有一个整数N,以下是一个N*N的方阵,代表各处的高度。 输入范围: 2 ≤ N ≤ 300 0 ≤ Height ≤ 10000000
输出
输出一个整数,代表最少等待时间T
样例输入
样例输入1:
2 0 2 1 3
样例输入2:
5 0 1 2 3 4 24 23 22 21 5 12 13 14 15 16 11 17 18 19 20 10 9 8 7 6
样例输出
样例输出1:
3
样例输出2:
16
提示
样例1:时间为3时,才可以游向平台(1,1),此时水位为3。 样例2:时间为16时,水位为16,此时才能保证(0,0)和(4,4)是联通的(请自行找出一条通路)。
答案与解析
参考答案
//动规+广搜+二分
//从(0,0)到(N-1,N-1)的各条路径最大值中的最小值。
//直接深搜和广搜会超时
#include <bits/stdc++.h>
using namespace std;
int n,m[305][305];// n 是矩阵的大小,m 存储矩阵元素
bool v[305][305];// v 记录矩阵中点是否被访问过
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
struct Point{
int x,y;
Point(int a,int b):x(a),y(b){}
};
bool is_reach(int t){// 判断是否在时间t内到达右下角坐标
if(m[0][0]>t) return false;// 左上角大于t无法到达
memset(v,0,sizeof(v));
v[0][0]=1;
queue<Point> myq;// 创建一个队列存储待访问的点
myq.push(Point(0,0));
while(!myq.empty()){
Point top=myq.front();
myq.pop();
// 到达右下角坐标,返回true
if((top.x==n-1)&&(top.y==n-1)) return true;
for(int i=0;i<4;i++){
int xx=top.x+dx[i];
int yy=top.y+dy[i];
// 如果已访问过或元素大于t,则无法继续前进
if(xx<0||xx>=n||yy<0||yy>=n||v[xx][yy]||(m[xx][yy]>t)) continue;
v[xx][yy]=1;// 标记坐标访问状态
myq.push(Point(xx,yy));// 将可继续访问的坐标加入队
}
}
return false;// 无法到达右下角坐标,返回false
}
int main()
{
memset(m,0,sizeof(m));
cin>>n;
int L=1e7,R=0;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++){
cin>>m[i][j];
L=min(L,m[i][j]);
R=max(R,m[i][j]);
}
int result=1e7;
while(L<R){// 二分查找
int mid=(L+R+1)/2;
if(is_reach(mid)){// mid值能到达右下角坐标
R=mid-1;
result=min(result,mid);// 更新结果
}
else L=mid;
}
cout<<result;
return 0;
}