首页 > 代码库 > 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 最长不下降序列