poj 2201構造

このテーマの构造方法はまだとても良いと思うべきで、まずaに小さいから大きいまで顺番に并べて、それから顺番にデータを挿入して、1本の二叉を构筑して木を探して、その上50000のデータ、nlognのやり方、やはりとても良いべきです.しかし、この問題の符号化は想像以上に面倒で、符号化が完了するとtleに戻った.
理解できないことを表して、1つの大きいデータを生成した後に、並べ替えた後にkも秩序があるならば、それでは二叉木が退化して、n*nの複雑さ.単純なグラフでは、データを挿入する後続または前駆体を探して、どの位置から挿入するかを探して最適化を見つけることができ、複雑さを大幅に安定させることができます.これを探す仕事はsetに任せて完成すればいい.
 

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <set>

using namespace std;

const int maxn=5e4+9;

int lon,f[maxn];

struct D

{

    int a,k,id;

    bool operator <(const D & xx) const

    {

        return k<xx.k;

    }

}data[maxn];



bool cmp(const D &p,const D &q)

{

    return p.a<q.a;

}



struct

{

    int l,r,id,fa;

}tr[maxn];



set <D> s;

int maxm;

void insert(int t)

{

//    cout<<t<<endl;

    int root;

    if(t!=1)

    {

        if(data[t].k>data[maxm].k)

        {

            root=f[data[maxm].id];

            maxm=t;

        }

        else root=f[s.lower_bound(data[t])->id];

    }

    else

    {

        root=1;

        maxm=1;

    }

    while(tr[root].id!=0)

    {

//        cout<<root<<endl;

        if(data[t].k<data[tr[root].id].k)

        {

            if(tr[root].l==0)

            {

                tr[root].l=++lon;

                tr[lon].fa=root;

            }

            root=tr[root].l;

        }

        else

        {

            if(tr[root].r==0)

            {

                tr[root].r=++lon;

                tr[lon].fa=root;

            }

            root=tr[root].r;

        }

    }

    tr[root].id=t;

    f[data[t].id]=root;

    s.insert(data[t]);

}



int main()

{

//    freopen("in.txt","r",stdin);

//    freopen("out.txt","w",stdout);

    int n;

    while(scanf("%d",&n)!=EOF)

    {

        for(int i=1;i<=n;i++)

        {

            scanf("%d %d",&data[i].k,&data[i].a);

            data[i].id=i;

        }

        sort(data+1,data+1+n,cmp);

        memset(tr,0,sizeof(tr));

        lon=1;

        for(int i=1;i<=n;i++)

        insert(i);

        printf("YES
");

        for(int i=1;i<=n;i++)

        {

            printf("%d %d %d
",data[tr[tr[f[i]].fa].id].id,data[tr[tr[f[i]].l].id].id,data[tr[tr[f[i]].r].id].id);

        }

    }

    return 0;

}