首页 > 代码库 > NYOJ 214 单调递增子序列nlogn
NYOJ 214 单调递增子序列nlogn
普通的思路是O(n2)的复杂度，这个题的数据量太大，超时，这时候就得用nlogn的复杂度的算法来做，这个算法的主要思想是只保存有效的序列，即最大递增子序列，然后最后得到数组的长度就是最大子序列。比如序列7 8 9 1 2 3 来说， 就是先把第一个数输入到数组中，然后继续输入后面的数，每输入一个数都要和最后一个数比较，因为这时最后一个数一定是有效序列中最大的，如果大于最后一个数，那么就直接将它放到数组的最后就行了，如果不大于最后一个数的话，就找到第一个比他大的数，然后替换它，样例中，先输入进去7， 然后再输入8，因为8 > 7， 所以直接将8放到数组的最后，同理，9也是，当输入到1的时候，判断它不比9大，这时候就需要找第一个比1大的数，这时候就用二分查找就行了，因为这个数组这样输入进去的话，肯定是有序的，找到第一个比他大的数是7，那么就替换7，现在数组中的元素分别是1, 8, 9,继续输入2，判断它不比数组的最后一个元素大，这时候继续二分找第一个比它大的，那么将替换8，同理3将会替换9，最后数组的元素分别是1， 2， 3,这是用贪心的策略来做的，因为只有保存最小的，后面的数组成最长序列的机会才会更大，所以要保存最小的，代码如下;
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 #include <vector> 5 using namespace std; 6 const int N = 100000 + 10; 7 int a[N];//保存当前最大的序列 8 int e;//表示当前数组中有几个元素 9 void replace_value(int n)//二分法查找替换10 {11 int left = 0, right = e;12 int mid = (left + right) >> 1;13 while (left < right)14 {15 if (left + 1 == right)16 {17 if (a[right] != n)//替换右值18 a[right] = n;19 return;20 21 }22 if (a[mid] == n)23 return;24 if (a[mid] > n)25 right = mid;26 else27 left = mid;28 mid = (left + right) >> 1;29 }30 }31 int main()32 {33 int n;34 while (~scanf("%d", &n))35 {36 e = 0;37 memset(a, 0, sizeof(a));38 a[0] = -2147483648;39 int t;40 for (int i = 0; i < n; i++)41 {42 43 scanf("%d", &t);44 if (t > a[e])//如果大于当前已有的数中最大的， 就将它添加到数组中45 a[++e] = t;46 else47 replace_value(t);48 }49 cout << e << endl;50 }51 return 0;52 }
下面这个代码的思想和上面的基本相同，我是看的网上的，大体思路就是先将数据输入到一个数组中，然后在一个一个的判断，找每个元素应该在的位置，也就是上面的那种思想，不过不如上面的那个简单
1 #include <stdio.h> 2 3 const int N = 100000 + 10; 4 int a[N], b[N];//a来存放输入的元素，b来存放当前最长子序列元素 5 //寻找n所在b当中的位置，二分查找，时间复杂度logn; 6 int search_pos(int n, int len) 7 { 8 int left = 1, right = len; 9 int mid = (left + right) >> 1;10 while (left <= right)11 {12 if (b[mid] == n)13 return mid;14 else if (b[mid] < n)15 left = mid + 1;16 else 17 right = mid - 1;18 mid = (left + right) >> 1;19 }20 return left;21 }22 int main()23 {24 int n;25 while (~scanf("%d", &n))26 {27 for (int i = 0; i < n; i++)28 scanf("%d", &a[i]);29 b[1] = a[0];30 int len = 1;31 int j;32 for (int i = 1; i < n; i++)33 {34 j = search_pos(a[i], len);//找到第一个比他大的位置，如果已经是最大，那么就是b数组的最后一个位置 35 b[j] = a[i];36 if (j > len)//如果是最后一个位置，len更新为j 37 len = j;38 }39 printf("%d\n", len);40 }41 return 0;42 }
NYOJ 214 单调递增子序列nlogn
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。