《信息学奥赛一本通》分治算法 找数 例题

【描述】

给一个长度为n的单调递增的正整数序列，即序列中每一个数都比前一个数大。
有m个询问，每次询问一个x，问序列中最后一个小于等于x的数是什么？

【输入】

第一行两个整数n，m。
接下来一行n个数，表示这个序列。
接下来m行每行一个数，表示一个询问。

【输出】

输出共m行，表示序列中最后一个小于等于x的数是什么。
假如没有，则输出-1.

【样例输入】

5 3
1 2 3 4 6
5
1
3

【样例输出】

4
1
3

【分析】

用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] 3.重复执行二分操作知道left>right。
最终循环结束时一定是left=right+1，所以最后的结果为right指向的值。

#include 
using namespace std;
int main ()
{int n,m,a[10000];cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];}a[0]=-1;for(int i=1;i<=m;i++){int x;cin>>x;int left=1,right=n,mid;while(left<=right){mid=(left+right)/2;if(a[mid]<=x){left=mid+1;}else{right=mid-1;}}cout<

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！