首页 > 代码库 > SGU 199. Beautiful People 二维LIS
SGU 199. Beautiful People 二维LIS
第一维排序 第二维LIS
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; int dp[100010]; int p[100010]; struct node { int x, y, id; }a[100010]; bool cmp(node a, node b) { if(a.x != b.x) return a.x < b.x; return a.y > b.y; } void print(int x) { if(p[x] == -1) { printf("%d", a[x].id); return; } print(p[x]); printf(" %d", a[x].id); } int main() { int n; while(scanf("%d", &n) != EOF) { memset(dp, -1, sizeof(dp)); memset(p, -1, sizeof(p)); for(int i = 1; i <= n; i++) { scanf("%d %d", &a[i].x, &a[i].y); a[i].id = i; } sort(a+1, a+n+1, cmp); dp[1] = 1; int len = 1; for(int i = 2; i <= n; i++) { int l = 1, r = len; while(l <= r) { int m = (l + r) >> 1; if(a[dp[m]].y < a[i].y) l = m+1; else r = m-1; } dp[l] = i; p[i] = dp[l-1]; if(l > len) len = l; } //sort(dp+1, dp+len+1); printf("%d\n", len); print(dp[len]); puts(""); } return 0; }
SGU 199. Beautiful People 二维LIS
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。