移动盒子——双向链表

超、凢脫俗 2022-05-15 14:36 95阅读 0赞

移动盒子UVa 12657

你有一行盒子，从左到右依次编号为1,2,3,…,n。可以执行以下4种指令：

1 x y：表示把盒子x移动到盒子y的左边（如果x已经在y的左边则忽略此指令）。  
2 x y：表示把盒子x移动到盒子y的右边（如果x已经在y的右边则忽略此指令）。  
3 x y：表示交换盒子x和y的位置。  
4：表示反转整条链。

指令保证合法，即x不等于y。

例如当n=6时在初始状态盒子序列为为：1 2 3 4 5 6；  
执行1 1 4后，盒子序列为：2 3 1 4 5 6；  
接下来执行2 3 5，盒子序列变为：2 1 4 5 3 6；  
再执行3 1 6，盒子序列变为：2 6 4 5 3 1；  
最终执行4，盒子序列变为：1 3 5 4 6 2。

【输入格式】  
输入包含不超过10组数据，每组数据第一行为盒子数n和指令m，以下m行每行包含一条指令。  
【输出格式】  
每组数据输出一行，即所有奇数位置的盒子编号之和。位置从左到右编号为1~n。  
【输入样例】  
6 4  
1 1 4  
2 3 5  
3 1 6  
4  
6 3  
1 1 4  
2 3 5  
3 1 6  
100000 1  
4  
【输出样例】  
12  
9

没有用C语言写，太麻烦了。

这里直接使用list容器进行模拟。（由于C++是自学的，容器也不咋会用，回头补补知识）

代码模拟：

//移动盒子——链表实现
    //dacao
    //2018/10/29
    #include<iostream>
    #include<list>
    using namespace std;
    
    int main()
    {
    	int n,m;
    	int op,x,y;
    	int i;
    	while(cin>>n>>m)
    	{
    		list<int> box;
    		list<int>::iterator it,itx,ity;
    		for(i=1;i<=n;i++)
    			box.push_back(i);
    		while(m--)
    		{
    			cin>>op;
    			if(op==4)
    			{
    				box.reverse();
    				continue;
    			}
    			
    			cin>>x>>y;
    			for(it=box.begin();it!=box.end();it++)
    			{
    				if(*it==x)
    					itx=it;
    				if(*it==y)
    					ity=it; 
    			}
    			
    			if(op==1)
    			{
    				box.insert(ity,*itx);
    				box.erase(itx);
    			}
    			
    			if(op==2)
    			{
    				box.insert(++ity,*itx);
    				box.erase(itx);
    			}
    			
    			
    			if(op==3)
    			{
    				box.insert(ity,*itx);
    				box.insert(itx,*ity);
    				box.erase(itx);
    				box.erase(ity);
    			}	
    		}	
    		int sum=0;
    		it=box.begin();
    		for(i=1;i<=n;i++)
    		{
    			if(i%2==1)
    				sum+=*it;
    			it++;
    		}
    		
    		cout<<sum<<endl;	
    	}
    	return 0;
    }

当然，这样写的结果会超时，答案是用数组来代替双向链表，且处理很有技巧[uva12657 移动盒子][uva12657]

链接中，有一行代码看不懂~

`想不通：if(p == 3 && right[y] == x) swap(x, y);`

代码来自：[https://blog.csdn.net/laddie132/article/details/48289137?utm\_source=blogxgwz7][https_blog.csdn.net_laddie132_article_details_48289137_utm_source_blogxgwz7]

#include<cstdio>
    #include<cstdlib>
    #include<algorithm>
    using namespace std;
    #define MAXL 100010
     
    int right[MAXL], left[MAXL];
     
    inline void link(int l, int r) {
    	right[l] = r;
    	left[r] = l;
    }
     
    int main() {
    //	freopen("input.txt","r",stdin);
    	int n, m, cases = 1;
    	while(scanf("%d%d", &n, &m) != EOF) {
    		int i, sta = 0;
    		right[n] = 0;
    		left[0] = n;
    		for(i = 0; i < n; i++) {
    			link(i, i+1);
    		}
    		for(i = 1; i <= m; i++) {
    			int p, x, y;
    			scanf("%d", &p);
    			if(p == 4) sta = !sta;
    			else{
    				scanf("%d%d", &x, &y);
    				if(p == 3 && right[y] == x) swap(x, y);
    				if(sta && (p == 1 || p == 2)) p = 3 - p;
    				if(p == 1 && right[x] == y) continue;
    				if(p == 2 && right[y] == x) continue;
    			}
    			int lx = left[x], rx = right[x], ly = left[y], ry = right[y];
    			switch (p) {
    				case 1 : {
    					link(lx, rx);
    					link(ly, x);
    					link(x, y);
    					break;
    				}
    				case 2 : {
    					link(lx, rx);
    					link(x, ry);
    					link(y, x);
    					break;
    				}
    				case 3 : {
    					link(lx, y);
    					link(x, ry);
    					if(rx == y) link(y, x);
    					else{
    						link(y, rx);
    						link(ly, x);
    					} 
    					break;
    				}
    				default : break;
    			}
    		}
    		long long ans = 0;
    		int b = 0;
    		for(i = 1; i <= n; i++) {
    			b = right[b];
    			if(i % 2 == 1) ans += b;
    		}	
    		if(sta && n % 2 == 0) ans = (long long)n * (n + 1) / 2 - ans;
    		printf("Case %d: %lld\n", cases++, ans);
    	}
    	return 0;
    }

[uva12657]: https://blog.csdn.net/qq_35546348/article/details/51870824?utm_source=blogxgwz0
[https_blog.csdn.net_laddie132_article_details_48289137_utm_source_blogxgwz7]: https://blog.csdn.net/laddie132/article/details/48289137?utm_source=blogxgwz7