首页 > 代码库 > 关于lower_bound()的用法--NYOJ 201作业题

关于lower_bound()的用法--NYOJ 201作业题

2024-08-04 10:14:13   220人阅读

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作业题


联系
我们