主要内容 #
- 问题描述
- 算法分析
- 参考程序
1. 问题描述 #
给一个长度为n的单调递增的正整数序列,即序列中每一个数都比前一个数大。
有m个询问,每次询问一个x,问序列中最后一个小于等于x的数是什么?
输入描述
第一行两个整数n,m。
接下来一行n个数,表示这个序列。
接下来m行每行一个数,表示一个询问。
输出描述
输出共m行,表示序列中最后一个小于等于x的数是什么。
假如没有,则输出-1.
输入样例
5 3
1 2 3 4 6
5
1
3
输出样例
4
1
3
2. 算法分析 #
用left表示序列的左边界,用right表示序列的右边界,[left,right]组成序列。
一开始left=1,right=n。序列已经按照升序排好,保证了二分的有序性。
每一次进行二分的步骤:
1.取序列区间的中间值mid=(left+right)/2;
2.判断mid与x的关系,如果a[mid]>x,所以区间[mid,right]直接排除,修改right=mid-1;
如果a[mid]
最终循环结束时一定是left=right+1,根据二分的第2步的做法我们知道right的右边一定都是大于x的,left的左边都是小于x的,所以最终答案是right指向的数。right=0就是题目中输出-1的情况。
3. 参考程序 #
#include<iostream> using namespace std; int n, m, a[110000]; int main(){ cin >> n >> m; //输入n和m for(int i = 1; i <= n; ++i){ cin >> a[i]; } a[0] = -1; //如果没有小于等于x的数最终会输出-1; for(int i = 1; i <= m; ++i){ int x; int left = 1, right = n, mid; //左右两个指针 cin >> x; while(left <= right){ //当左指针一直小于等于右指针时不断循环二分 mid = (left + right) / 2; if(a[mid] <= x) left = mid + 1; else right = mid - 1; } cout << a[right] << endl; //输出结果 } return 0; }