首页 > 代码库 > AC_Dream 1216 G - Beautiful People
AC_Dream 1216 G - Beautiful People
题意:
有n个人每人有一个力气值Si,美丽值Bi,满足Bi>Bj&&Si>Sj 或者 Bi<Bj&&Si<Sj 的人可以
一起参见晚会,问最多有多少人可以一起参见晚会。
思路: 我们根据S从小到大将所有人排序,然后看B最长的上升子序列的长度求出来即可!
在排序中优先对S排序,S相等的则对B进行由大到小的排序,why?
也就是对于S相同的,我们先选取B最大的值插入LIS中,因为比如 S1=1, B1 = 1
S1=1, B1 = 2, S1=1, B1 = 3, 如果不进行排序,直接按照求B中的lis,显然长度
为3,显然是不对的,因为相同的S中只能选择一个B出来!所以就要对S相同的B进行
降序排序! 这样就变成了一个裸lis!
1 #include<iostream> 2 #include<cmath> 3 #include<cstring> 4 #include<algorithm> 5 #include<cstdio> 6 #define N 100005 7 using namespace std; 8 9 struct node{10 int x, y;11 int p;12 };13 14 bool cmp(node a, node b){15 if(a.x == b.x)16 return a.y > b.y;17 return a.x < b.x;18 }19 20 bool myCmp(node a, node b){21 return a.y <= b.y;//这里要写成 <=;因为upper_bound返回的是“元素值 >插入值”22 //最后一个插入值的位置,元素值 == 插入值的时候,默认 元素值23 // >插入值,但在该题中,相等的情况下不能算在lis中的! 24 }25 26 node a[N];27 node c[N];28 29 int pre[N], path[N];30 31 int main(){32 int n;33 while(scanf("%d", &n) != EOF){34 for(int i=0; i<n; ++i)35 scanf("%d%d", &a[i].x, &a[i].y), a[i].p = i+1;36 37 sort(a, a+n, cmp); 38 c[0] = a[0];39 pre[0] = 0;40 path[0] = 0;41 int len = 1;42 43 for(int i=1; i<n; ++i){44 int k = upper_bound(c, c+len, a[i], myCmp) - c;45 pre[i] = k ? path[k-1] : 0;//当前插入节点i的位置为k,它的前一个(k-1位置)元素的序号! 46 path[k] = i;//当前插入k位置的节点的序号 47 c[k] = a[i];48 if(k+1 > len) len = k+1;49 }50 int tmp = path[len-1];51 printf("%d\n", len);52 printf("%d", a[path[len-1]].p);53 for(int i=len-2; i >= 0; --i){54 tmp = pre[tmp];55 printf(" %d", a[tmp].p);56 }57 printf("\n");58 59 }60 return 0;61 }
AC_Dream 1216 G - Beautiful People
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。