[RQNOJ469 喜鹊 (HDOJ3552 I can do it!加强版)]【叉姐NOIP模拟题】【排序】【平衡树】

【题目大意】

给定n个物品,第i个物品有三个属性Ai,Bi,Ci。然后把这个n个物品分别分到3个集合中(集合可以为空),使得A集合中的物品的Max{Ai}+B集合中的物品的Max{Bi}+C集合中物品的Max{Ci}最小。(空集算作0)

【算法分析】

HDOJ3552是只有两个属性,那么按Ai排序,然后枚举Max{Ai}。然后剩下的另一边的Max{Bi}加起来就是当前值。

然后对于本题。依然按Ai排序,仍然从大到小枚举Max{Ai}。然后对剩下的另一边维护上面那个问题。

显然,若存在Bi<=Bj Ci<=Cj,那么i这个物品就没用了。那么我们可以维护一个线性表,使得他关于Bi递增。同时,删掉多余的物品以后,关于Ci递减。那么很显然,我们取某一个物品截开,那么这边取的值就是Bi+Ci+1,然后这种动态线性表显然就可以用平衡树维护。然后为了比较方便找前驱和后继,我用了Splay。

【其它】1Y。这次把Splay函数和rotate函数压了代码,Splay只有两个rotate,rotate里不用分类讨论。

【CODE】

#include

#include

#include

#include

#include

using namespace std;

const int N=105555;

const int INF=1000000000;

int n,root;

struct Node{int x,y,z;}a[N];

int pre[N],best[N],w[N],ch[N][2];

bool cmp(const Node &A,const Node &B){

     return A.x

}

void init(){

     int i;

     scanf("%d",&n);

     for (i=1;i<=n;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);

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

     memset(ch,0,sizeof(ch));

     memset(pre,0,sizeof(pre));

     root=n+1;

     ch[n+1][0]=n+2;

     pre[n+2]=n+1;

    

     a[n+1].y=INF; a[n+1].z=0;

     a[n+2].y= 0; a[n+2].z=INF;

    

     w[n+1]=INF; best[n+1]=0;

     w[n+2]=best[n+2]=0;

}

void update(int x){

     best[x]=INF;

     if (ch[x][0]) best[x]=min(best[ch[x][0]],best[x]);

     if (ch[x][1]) best[x]=min(best[ch[x][1]],best[x]);

     best[x]=min(w[x],best[x]);

}

void rotate(int x,int T){

     int y=pre[x];

     ch[y][!T]=ch[x][T];

     ch[x][T]=y;

     pre[x]=pre[y];

     pre[y]=x;

     pre[ch[y][!T]]=y;

     if (ch[pre[x]][0]==y) ch[pre[x]][0]=x;

                      else ch[pre[x]][1]=x;

     update(y);

     update(x);

}

void Splay(int x,int goal){

     int y,z;

     if (x==0 || x==goal) return;

     if (goal==0) root=x;

     while (pre[x]!=goal){

           y=pre[x]; z=pre[y];

           if (z!=goal) rotate(ch[z][0]==y^ch[y][0]==x?x:y,ch[y][0]==x);

           rotate(x,ch[pre[x]][0]==x);

     }

}

void Get_next(){

     int p=ch[root][1],q=root;

     while (p){

           q=p;

           p=ch[p][0];

     }

     Splay(q,0);

}

void Get_pre(){

     int p=ch[root][0],q=root;

     while (p){

           q=p;

           p=ch[p][1];

     }

     Splay(q,0);

}

bool Can_Insert(int i){

     int p=root,q;

     while (p){

           q=p;

           p=ch[p][a[p].y

     }

     Splay(q,0);

     if (a[q].y

     if (a[root].y>=a[i].y && a[root].z>=a[i].z) return false;

                                            else return true;

}

void (){

     int p=ch[root][0];

     while (ch[p][1]) p=ch[p][1];

     Splay(p,root);

     ch[p][1]=ch[root][1];

     pre[ch[root][1]]=p;

     pre[p]=0;

     root=p;

}

void Delete_Useless_Node(int i){

     while (1){

       if (a[root].y>a[i].y) Get_pre();

       if (a[root].y<=a[i].y && a[root].z<=a[i].z)

         ();

       else

         break;

     }

}

void Insert(int i){

     int p=root,q;

     while (p){

           q=p;

           p=ch[p][a[p].y

     }

     pre[i]=q;

     ch[q][a[q].y

     Splay(i,0);

     p=ch[i][1];

     while (ch[p][0]) p=ch[p][0];

     w[i]=a[i].y+a[p].z;

     Splay(p,i);

     update(i);

     Get_pre();

     w[root]=a[root].y+a[i].z;

     update(root);

}

void Try_Insert(int i){

     if (!Can_Insert(i)) return;

     Delete_Useless_Node(i);

     Insert(i);

}

    

void work(){

     int i,ans=INF,now;

     a[0].x=0;

     for (i=n;i>=0;i–){

         now=a[i].x;

         now+=best[root];

         if (now

         Try_Insert(i);

     }

     printf("%dn",ans);

}

int main(){

    init();

    work();

    return 0;

}

留下评论

您的电子邮箱地址不会被公开。 必填项已用 * 标注