Algorithm: 移动盒子

原创
2016/06/12 18:29
阅读数 95

题目意思是说,给出一个数n,表示存在一个整数序列1……n,然后进行四种操作:

操作一:输入x,y,表示将x移到y的左边(若x本来就在y的左边则忽略);

操作二:输入x,y,表示将x移到y的右边(若x本来就在y的右边则忽略);

操作三:输入x,y,表示交换x和y。

操作四:将整个序列倒置。

最后要求的是操作后的整个序列奇数项的和。

数据为100000,直接模拟肯定超时,用STL的链表也会超,我的想法是用数组模拟链表,left[i]和right[i]数组分别存放i的左值和右值。在整个过程中,逆序操作最耗时间,由于题目只需要求奇数项的和,在进行逆序操作时,我们没必要真真进行操作,只需要记录逆序的次数即可,若是奇数次,则最后求整个序列的偶数项之和,偶数次就是求奇数项之和。还有一点就是,操作四的进行与否会对前两种操作有一点影响,需要稍作处理。详细过程见代码:

#include <iostream>
#include <memory>
#include <new>

class Boxes{
	private:
		
		//用于构建双向链表. 
		std::unique_ptr<int[]> left;     //当下标为i的时候i的左侧的内容. 
		std::unique_ptr<int[]> right;    //当下标为i的时候i的右侧的内容. 
		
		bool flag; //判断是否反转了链表.
		unsigned int suffix;
		unsigned int X;
		unsigned int Y;
		
		void link(const int& lh, const int& rh)noexcept;
		
		public:
			
		Boxes(const std::size_t& size);
		
		~Boxes() = default;
		
		void moveBox();
};

Boxes::Boxes(const std::size_t& size)try
      :left(nullptr),
       right(nullptr),
       flag(false)
{
	if(size == 0){
		throw std::bad_alloc();
	}
	
	(this->left).reset(new int[size+1]);
	(this->right).reset(new int[size+1]);
	
	//构建双向链表. 
	for(std::size_t i=1; i<=size; ++i){
		(this->left)[i] = i-1;
		(this->right)[i] = (i+1)%(size+1);
	}
	
	(this->right)[0] = 1;
	(this->left)[0] = size;
	
	/*for(std::size_t i=0; i<=size; ++i){
		std::cout<< "[" << i << "]:" << (this->left)[i] << " ";
		
	}
	
	std::cout<< std::endl;
	for(std::size_t i=0; i<=size; ++i){
		std::cout<< "[" << i << "]:" << (this->right)[i] << " ";
	}*/
	
}catch(const std::bad_alloc& error){
	std::cout<< "fail to allocate" <<std::endl;
}

void Boxes::link(const int& lh, const int& rh)noexcept
{
	(this->left)[rh] = lh;
	(this->right)[lh] = rh;
}

void Boxes::moveBox()
{
	while( std::cin>>(this->suffix) ){
			if((this->suffix) == 4){
		(this->flag) = !(this->flag); //如果等于4那么反转. 
		
	}else{
		std::cin>>(this->X);
		std::cin>>(this->Y);
		
		//在未被反转过的情况下盒子Y的右侧正好是盒子X. 
		if((this->suffix) == 3 && (this->right)[this->Y] == this->X) std::swap(this->X, this->Y); 
		
		//判断是否在需要被交换的节点不相邻的情况下,且已经执行了逆序操作的情况下 使原来的左边变右边. 
		if((this->suffix) != 3 && (this->flag) == true) (this->suffix) = 3 - (this->suffix);
		
		//判断反转后是否盒子X正好位于盒子Y的左侧. 
		if((this->suffix) == 1 && (this->X) == (this->left)[this->Y]);
		
		//判断反转后是否盒子X正好位于盒子Y的右侧. 
		if((this->suffix) == 2 && (this->X) == (this->right)[this->Y]);
		
		int lX=(this->left)[this->X];  //获得坐标为X的左侧的数据. 
		int rX=(this->right)[this->X]; //获得坐标为X的右侧数据. 
		int lY=(this->left)[this->Y];  //获得坐标为Y的左侧数据. 
		int rY=(this->right)[this->Y]; //获得坐标为Y的右侧数据.
		
		if((this->suffix) == 1){  //将X坐标处的数据移到Y坐标处数据的左边. 
			this->link(lX, rX); 
			this->link(lY, (this->X));
			this->link((this->X), (this->Y));
			
		}else if((this->suffix) == 2){ //将X坐标处的数据移动到Y的右边. 
			this->link(lX, rX);
			this->link((this->Y), (this->X));
			this->link((this->X), lY);
			
		}else if((this->suffix) == 3){ //交换坐标X处和坐标Y处的数据. 
			
			if((this->left)[this->X] == Y){  //X和Y相邻. 
				this->link(lX, (this->X));
				this->link((this->Y), (this->X));
				this->link((this->X), rY);
				
			}else{
				this->link(lX, (this->Y));
				this->link((this->Y), rX);
				this->link(lY, (this->X));
				this->link((this->X), rY);
			}
		}
	}
	}
}

int main()
{
	Boxes box(3);
	box.moveBox();
	
	return 0;
}

 

展开阅读全文
加载中

作者的其它热门文章

打赏
0
1 收藏
分享
打赏
0 评论
1 收藏
0
分享
返回顶部
顶部
返回顶部
顶部