【CERC2007】机器排序-白红宇

【CERC2007】机器排序

阅读量：5145 次

发布时间：2019-06-13

本文共 3662 字，大约阅读时间需要 12 分钟。

P2438 - 【CERC2007】机器排序

Description

在布拉格捷克理工大学（Czech Technical University）某个幽深的角落，有一些实验室用来检测各种材料的机械和电气性能。在昨天的一项展示中，你已经见识了其中的一间是如何变成全新的多媒体实验室的。但那里仍然有别的实验室，服务于它们最初的用途。

在这个任务中，你将要给这样的一间实验室中一个搬运样品的机器人编写程序。设想有一些材料样品在一条传送带上排成一排。这些样品有不同的高度，这可能会给接下来的处理带来麻烦。为了消除这样的隐患，我们需要将这些样品按高度升序排列。

排序由一条机械臂完成，它可以抱起一些连续的样品并且将它们掉头，这样一来它们在传送带上的顺序就被翻转。换句话说，一个操作可以翻转A到B（含两端）的样品顺序。

给样品排序的一个可能方式是找到高度最小的样品P1，将1到P1的样品顺序翻转。这将使得P1成为第一个样品。接下来我们找到高度第二小的样品P2，将2到P2的样品顺序翻转。然后找到高度第三小的样品，以此类推。

这张图片展示了一个含6个样品的简单例子。高度最小的样品在4号位置，因此机械臂旋转前4个样品。高度第二小的样品在6号位置，因此下一个操作是翻转2-6号样品位置。第三步是翻转3-4号样品位置，以此类推。

你的任务是找到用上述算法给样品排序时正确的翻转操作序列。如果不止一个样品有相同的高度，必须保持它们的顺序不变：在初始序列中靠前的在最终序列中也应该靠前。

Input

输入包含多组数据。

每组数据有两行。第一行是一个正整数N，即样品个数（1<=N<=100000）。

第二行有N个由空格分隔的正整数，即各样品的高度，按最初的样品顺序给出。

输入结束标志为一行一个0。

Output

对每组数据，输出一行恰好N个整数P1,P2,...,PN，彼此由空格分隔。每个Pi应该是一个正整数（1<=Pi<=N），给出了第i次翻转操作前第i个样品的位置。

注意如果一个样品已经站在了正确的位置Pi上，你也应该输出Pi，表明“Pi到Pi的样品”（即Pi一个样品）应该被翻转。

Sample Input

Sample Output

6 4 5 6 6 
2 4 4 
 

首先将输入的数排个序，然后用一个id数组记录位置为ｉ的点的大小排名。

然后就根据位置的中序遍历来建树。

为了保持树的平衡，所以先把位置１定为根，把位置ｎ定为１的右儿子。

然后用一个ma数组记录排行为ｉ的数在平衡树中的结点编号，这时id数组派上用场了。

然后每次要查询排名为ｉ的数，所以可以先把排名为ｉ的数旋转到根，然后答案就左子树的size+1。然后删掉根节点。

关于删除，若没有后继可以直接删掉，否则要先找到根节点的后继，记得一边找一边下放。然后旋转到根，再把原来的根的左子树接到这个点的左子树上就可以了。

然后就是区间翻转的down函数：

1 void　down(int x){2   if(flip[x]){3     flip[x]=0;4     flip[ch[x][0]]^=1;5     flip[ch[x][1]]^=1;6     swap(ch[x][0],ch[x][1]);7   }8 }

　旋转的时候要记得把pre[pre[x]],pre[x],x依次下放。

反正这是一道很鬼的题。

1 #include
        
           2 #include
           3 #include
          
             4 #include
           
              5 #include
            
               6 #include
             
               7 #include
              
                8 #include
               
                 9 #include
                
                  10 #include
                 
                   11 #include
                  
                    12 #include
                   
                     13 #include
                    
                      14 #define maxn 100010 15 using namespace std; 16 int pre[maxn],ch[maxn][2],id[maxn],size[maxn],tot=0,root=0,flip[maxn],ma[maxn]; 17 struct data{ 18 int num,id; 19 }in[maxn]; 20 void updata(int x){ 21 size[x]=size[ch[x][0]]+size[ch[x][1]]+1; 22 } 23 void down(int x){ 24 if(flip[x]){ 25 flip[x]=0; 26 flip[ch[x][0]]^=1; 27 flip[ch[x][1]]^=1; 28 swap(ch[x][0],ch[x][1]); 29 } 30 } 31 void Rotate(int x,int kind){ 32 int y=pre[x]; 33 down(y); 34 down(x); 35 ch[y][!kind]=ch[x][kind]; 36 pre[ch[x][kind]]=y; 37 if(pre[y]) 38 ch[pre[y]][ch[pre[y]][1]==y]=x; 39 pre[x]=pre[y]; 40 ch[x][kind]=y; 41 pre[y]=x; 42 updata(y); 43 } 44 inline void Splay(int r,int goal){ 45 down(r); 46 while(pre[r]!=goal){ 47 int y=pre[r],z=pre[y]; 48 if(z!=0) down(z); 49 down(y),down(r); 50 if(pre[pre[r]]==goal) 51 Rotate(r,ch[pre[r]][0]==r); 52 else{ 53 int kind=ch[pre[y]][0]==y; 54 if(ch[y][kind]==r){ 55 Rotate(r,!kind); 56 Rotate(r,kind); 57 } 58 else{ 59 Rotate(y,kind); 60 Rotate(r,kind); 61 } 62 } 63 } 64 updata(r); 65 if(goal==0) root=r; 66 } 67 void newnode(int &x,int fa){ 68 x=++tot; 69 pre[x]=fa; 70 ch[x][1]=ch[x][0]=0; 71 size[x]=1; 72 flip[x]=0; 73 } 74 void build(int &x,int l,int r,int fa){ 75 if(l>r) return; 76 int mid=(l+r)>>1; 77 newnode(x,fa); 78 ma[id[mid]]=x; 79 build(ch[x][0],l,mid-1,x); 80 build(ch[x][1],mid+1,r,x); 81 updata(x); 82 } 83 void del_root(){ 84 int t=root; 85 if(ch[root][1]){ 86 root=ch[root][1]; 87 while(1){ 88 down(root); 89 if(size[ch[root][0]]==0) break; 90 root=ch[root][0]; 91 } 92 Splay(root,0); 93 ch[root][0]=ch[t][0]; 94 if(ch[t][0]) pre[ch[t][0]]=root; 95 } 96 else root=ch[root][0]; 97 pre[root]=0; 98 updata(root); 99 }100 void solve(int n){101 for(int i=1;i<=n;i++){102 Splay(ma[i],0);103 printf("%d ",i+size[ch[root][0]]);104 flip[ch[root][0]]^=1;105 del_root();106 }107 }108 bool cmp(const data &a,const data &b){109 if(a.num!=b.num) return a.num

转载于:https://www.cnblogs.com/pantakill/p/6679611.html

你可能感兴趣的文章