首页 > 代码库 > BZOJ 1852 最长不下降序列
BZOJ 1852 最长不下降序列
数据过水。此非正解。
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define maxn 100500using namespace std;int n,ret=0;struct pnt{ int a,b;}p[maxn];bool cmp1(pnt x,pnt y){ if ((x.b>=y.a) && (x.a>y.b)) return false; else if ((x.b>=y.a) && (x.a<=y.b)) return x.b<y.b; else if ((x.b<y.a) && (x.a>y.b)) return x.a<y.a; else return true;}bool cmp2(pnt x,pnt y){ if (x.a==y.a) return x.b>y.b; return x.a>y.a;}inline int read(){ int data=http://www.mamicode.com/0;char ch; while (ch<‘0‘ || ch>‘9‘) ch=getchar(); while (ch>=‘0‘ && ch<=‘9‘) { data=data*10+ch-‘0‘; ch=getchar(); } return data;}int main(){ n=read(); for (register int i=1;i<=n;i++) p[i].a=read(),p[i].b=read(); int ans=0,mx=0; sort(p+1,p+n+1,cmp1); for (register int i=1;i<=n;i++) { if (p[i].a>mx) { ans++; mx=max(mx,p[i].b); } } ret=max(ret,ans); sort(p+1,p+n+1,cmp2); ans=1;mx=p[1].a; for (register int i=2;i<=n;i++) { if (mx>p[i].b) { ans++; mx=p[i].a; } } ret=max(ret,ans); printf("%d\n",ret); return 0;}
BZOJ 1852 最长不下降序列
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。