首页 > 代码库 > 关于lower_bound()的用法--NYOJ 201作业题
关于lower_bound()的用法--NYOJ 201作业题
lower_bound它有三个参数, 第一个和第二个是给定区间起点和终点的指针,第三个参数是要查找的数,它的作用原理是在给定的区间中进行二分查找,这个二分区间是前开后闭的,他返回第一个大于等于它的函数指针,例如数组 a[100] = {3, 4, 5, 6, 7, 10, 12, 34, 55}; 想找2的话,返回就返回第一个a[0]的位置,找8,就返回a[5]的位置,如果找99,比任何数都大,那么就返回数组中最后一个的下一个位置,就返回9,所以,这是可以越界的,有个测试程序,可以看下他的结果
1 #include <stdio.h> 2 #include <string.h> 3 #include <algorithm> 4 #include <vector> 5 using namespace std; 6 int main() 7 { 8 int a[100] = {3, 4, 5, 6, 7, 10, 12, 34, 55}; 9 int b = lower_bound(a, a + 9, 2) - a;10 //查看数组是否改变 11 for (int i = 0; i < 9; i++)12 printf("%d ", a[i]);13 puts("");14 15 int c = lower_bound(a, a + 9, 8) - a;16 int d = lower_bound(a, a + 9, 3) - a;17 int e = lower_bound(a, a + 9, 455) - a;18 printf("b = %d, c = %d, d = %d, e = %d\n", b, c, d, e);19 20 return 0;21 }
下面这道题,正好可以用下这个练练手,这个题就是将x拍完序之后,找 最长递增子序列,最长递减子序列 中的最大值,在找子序列位置时(用的O(nlog(n))的算法)用到这个,代码如下,也是这个题的最优代码:
#include <cstdio>#include <vector>#include <algorithm>#include <cstring>#include<functional>#define CLEAR(a, b) memset(a, b, sizeof(a))using namespace std; const int MAX = 10000 + 10;int y[MAX], dp1[MAX], dp2[MAX];int main(){ int N; scanf("%d", &N); while (N--) { CLEAR(y, 0); CLEAR(dp1, 0); CLEAR(dp2, 0); int n; scanf("%d", &n); int x; for (int i = 0; i < n; i++) { scanf("%d", &x); scanf("%d", &y[x-1]); } int num1 = 0, num2 = 0; int num = remove(y, y + MAX, 0) - y; for (int i = 0; i < num; i++) { int *p = lower_bound(dp1, dp1 + num1, y[i]); int *q = lower_bound(dp2, dp2 + num2, y[i], greater<int>()); if (p - dp1 == num1) num1++; if (q - dp2 == num2) num2++; *p = y[i]; *q = y[i]; } printf("%d\n", max(num1, num2)); } return 0;}
关于lower_bound()的用法--NYOJ 201作业题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。