首页 > 代码库 > zoj 2319 Beautiful People
zoj 2319 Beautiful People
题目链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1319
题目大意:就是求最长递增子序列,并输出位置。。。。
思路:先把s进行升序排列,然后把b按降序排列,最后把找出b的最长递增子序列。。。。
先给两个最长递增子序列的模板:了解更多轻点这儿。。。。。。
时间复杂度:O(log(n*n))
unsigned int LISS(const int array[], size_t length, int result[]) { unsigned int i, j, k, max; //变长数组参数,C99新特性,用于记录当前各元素作为最大元素的最长递增序列长度 unsigned int liss[length]; //前驱元素数组,记录当前以该元素作为最大元素的递增序列中该元素的前驱节点,用于打印序列用 unsigned int pre[length]; for(i = 0; i < length; ++i) { liss[i] = 1; pre[i] = i; } for(i = 1, max = 1, k = 0; i < length; ++i) { //找到以array[i]为最末元素的最长递增子序列 for(j = 0; j < i; ++j) { //如果要求非递减子序列只需将array[j] < array[i]改成<=, //如果要求递减子序列只需改为> if(array[j] < array[i] && liss[j] + 1> liss[i]) { liss[i] = liss[j] + 1; pre[i] = j; //得到当前最长递增子序列的长度,以及该子序列的最末元素的位置 if(max < liss[i]) { max = liss[i]; k = i; } } } } //输出序列 i = max - 1; while(pre[k] != k) { result[i--] = array[k]; k = pre[k]; } result[i] = array[k]; return max; }
时间复杂度:O(nlog(n))
unsigned int LISSEx(const int array[], size_t length, int result[]) { unsigned int i, j, k, l, max; //栈数组参数,C99新特性,这里的liss数组与上一个函数意义不同,liss[i]记录长度为i + 1 //递增子序列中最大值最小的子序列的最后一个元素(最大元素)在array中的位置 unsigned int liss[length]; //前驱元素数组,用于打印序列 unsigned int pre[length]; liss[0] = 0; for(i = 0; i < length; ++i) { pre[i] = i; } for(i = 1, max = 1; i < length; ++i) { //找到这样的j使得在满足array[liss[j]] > array[i]条件的所有j中,j最小 j = 0, k = max - 1; while(k - j > 1) { l = (j + k) / 2; if(array[liss[l]] < array[i]) { j = l; } else { k = l; } } if(array[liss[j]] < array[i]) { j = k; } //array[liss[0]]的值也比array[i]大的情况 if(j == 0) { //此处必须加等号,防止array中存在多个相等的最小值时,将最小值填充到liss[1]位置 if(array[liss[0]] >= array[i]) { liss[0] = i; continue; } } //array[liss[max -1]]的值比array[i]小的情况 if(j == max - 1) { if(array[liss[j]] < array[i]) { pre[i] = liss[j]; liss[max++] = i; continue; } } pre[i] = liss[j - 1]; liss[j] = i; } //输出递增子序列 i = max - 1; k = liss[max - 1]; while(pre[k] != k) { result[i--] = array[k]; k = pre[k]; } result[i] = array[k]; return max; }
AC code:
#include<iostream> #include<cmath> #include<cstdio> #include<algorithm> using namespace std; struct Node { int s,b,id; //记录s,b,还有开始的位置 }node[100010]; bool cmp(Node t1,Node t2) { return t1.s<t2.s||(t1.s==t2.s&&t1.b>t2.b); } unsigned int LISSEx(const Node array[], size_t length, int result[]) { unsigned int i, j, k, l, max; //栈数组参数,C99新特性,这里的liss数组与上一个函数意义不同,liss[i]记录长度为i + 1 //递增子序列中最大值最小的子序列的最后一个元素(最大元素)在array中的位置 unsigned int liss[length]; //前驱元素数组,用于打印序列 unsigned int pre[length]; liss[0] = 0; for(i = 0; i < length; ++i) { pre[i] = i; } for(i = 1, max = 1; i < length; ++i) { //找到这样的j使得在满足array[liss[j]] > array[i]条件的所有j中,j最小 j = 0, k = max - 1; while(k - j > 1) { l = (j + k) / 2; if(array[liss[l]].b < array[i].b) { j = l; } else { k = l; } } if(array[liss[j]].b < array[i].b) { j = k; } //array[liss[0]]的值也比array[i]大的情况 if(j == 0) { //此处必须加等号,防止array中存在多个相等的最小值时,将最小值填充到liss[1]位置 if(array[liss[0]].b >= array[i].b) { liss[0] = i; continue; } } //array[liss[max -1]]的值比array[i]小的情况 if(j == max - 1) { if(array[liss[j]].b < array[i].b) { pre[i] = liss[j]; liss[max++] = i; continue; } } pre[i] = liss[j - 1]; liss[j] = i; } //输出递增子序列 i = max - 1; k = liss[max - 1]; while(pre[k] != k) //记录排序后得到的最长递增子序列的位置 { result[i--] = k; k = pre[k]; } result[i] = k; return max; } int result[100010],array[100010]; int main() { int n,i; int T; scanf("%d",&T); while(T--) { scanf("%d",&n); for(i=0;i<n;i++) { scanf("%d%d",&node[i].s,&node[i].b); node[i].id=i+1; } sort(node,node+n,cmp); int len=LISSEx(node,n,result); printf("%d\n",len); for(i=0;i<len-1;i++) { printf("%d ",node[result[i]].id); } printf("%d\n",node[result[i]].id); } return 0; }
zoj 2319 Beautiful People
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。