【题目描述】
给一个长度为n的单调增的正整数序列&＃xff0c;即序列中每一个数都比前一个数大。有m个询问&＃xff0c;每次询问一个x&＃xff0c;问序列中最后一个小于等于x的数是什么&＃xff1f;
【输入】
序列中最后一个小于等于x的数
【输出】
输出共m行&＃xff0c;表示序列中最后一个小于等于x的数是多少。假如没有输出-1。
【输入样例】
5 3
1 2 3 4 6
5
1
3
【输出样例】
4
1
3
【算法分析】
写给新人&＃xff0c;dalao勿喷。虽然自己也是个新人蒟蒻。
无比基础的二分。二分这种东西思想无比简单&＃xff0c;然而代码敲起来就漏洞百出了。所以非常需要注意。
来看看核心代码&＃xff1a;
1 while(left<&＃61;right) //如果左最大值<&＃61;右最大值&＃xff0c;查找继续。
2 {
3 mid&＃61;(left&＃43;right)/2; //求中间值。
4 if(a[mid]<&＃61;x) //如果中间的数小于等于询问数
5 left&＃61;mid&＃43;1; //左边的值&＃61;中间值&＃43;1.往右挪。
6 else right&＃61;mid-1; //如果不是那样&＃xff0c;往左挪。
7 }
我们用输入样例来理解。
一共有五个数&＃xff0c;1,2,3,4,6。三个要询问的值&＃xff0c;4,1,3&＃xff08;此处以x&＃61;&＃61;4为例&＃xff09;我们能画图&＃xff1a;
left&＃61;1,right&＃61;n,所以此时求出mid的值&＃xff0c;为3。
1 if(a[mid]<&＃61;x) //如果中间的数小于等于询问数
2 left&＃61;mid&＃43;1; //左边的值&＃61;中间值&＃43;1.往右挪。
3 else right&＃61;mid-1; //如果不是那样&＃xff0c;往左挪。
接下来就看图了。
接下来的过程自个模拟一遍&＃xff0c;自然就能理解了。
【参考代码】
1 #include
2 using namespace std;
3 int main()
4 {
5 int n,m,a[110000];
6 cin>>n>>m;
7 for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;) cin>>a[i];
8 a[0]&＃61;-1;
9 for(int i&＃61;1;i<&＃61;m;i&＃43;&＃43;) //只用查询问个数的次数就好&＃xff0c;i<&＃61;m.
10 {
11 int x;
12 int left&＃61;1,right&＃61;n,mid;
13 cin>>x; //输入询问数。
14 while(left<&＃61;right) //如果左最大值<&＃61;右最大值&＃xff0c;查找继续。
15 {
16 mid&＃61;(left&＃43;right)/2; //求中间值。
17 if(a[mid]<&＃61;x) //如果中间的数小于等于询问数
18 left&＃61;mid&＃43;1; //左边的值&＃61;中间值&＃43;1.往右挪。
19 else right&＃61;mid-1; //如果不是那样&＃xff0c;往左挪。
20 }
21 cout<
22 }
23
24 }
京公网安备 11010802041100号