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