现在的位置: 首页 > 综合 > 正文

UVa Problem 10152 ShellSort (龟壳排序)

2012年09月15日 ⁄ 综合 ⁄ 共 2273字 ⁄ 字号 评论关闭
// ShellSort (龟壳排序)
// PC/UVa IDs: 110407/10152, Popularity: B, Success rate: average Level: 2
// Verdict: Accepted
// Submission Date: 2011-05-27
// UVa Run Time: 0.656s
//
// 版权所有(C)2011,邱秋。metaphysis # yeah dot net
//
// 如何移动才能实现最少移动步骤?这个问题花费了我一些时间去思考。考虑如下一个初始状态和最终
// 状态(为了解释方便,在乌龟的名字前面用方括号标记了序号):
//
// 初始状态:             最终状态:
// [4]Yertle            [1]Oscar
// [1]Oscar             [2]Baron
// [2]Baron             [3]Lord
// [3]Lord              [4]Yertle
// [5]King              [5]King
// [7]White             [6]Kong
// [6]Kong              [7]White
//
// 可以通过如下六步达到目标,六步是所需最少步骤。
// 
// [4]Yertle            [6]Kong                 [5]King
// [1]Oscar             [4]Yertle               [6]Kong
// [2]Baron             [1]Oscar                >>>>[4]Yertle
// [3]Lord      ==>>    [2]Baron       ==>>     [1]Oscar        ==>>
// [5]King              [3]Lord                 [2]Baron
// [7]White             >>>>[5]King             [3]Lord
// >>>>[6]Kong          [7]White                [7]White
//
// [4]Yertle            [3]Lord                 [2]Baron
// [5]King              [4]Yertle               [3]Lord
// [6]Kong              [5]King                 [4]Yertle
// [1]Oscar     ==>>    [6]Kong        ==>>     [5]King         ==>>
// [2]Baron             [1]Oscar                [6]Kong
// >>>>[3]Lord          >>>>[2]Baron            >>>>[1]Oscar
// [7]White             [7]White                [7]White
//
//
// [1]Oscar
// [2]Baron
// [3]Lord
// [4]Yertle
// [5]King
// [6]Kong
// [7]White
//
// 算法如下:假设有 n 只乌龟,编号为 1 ~ n,对于编号为 n 的乌龟,如果编号为 n - 1 的乌龟在
// 编号为 n 的乌龟的下方,将编号为 n - 1 的乌龟放到顶端,然后对编号为 n - 1,n - 2,... ,
// 2,1 的乌龟继续以上操作,直到排序完毕。
	
#include <iostream>
	
using namespace std;
	
#define MAXSIZE 200
	
#ifndef DEBUG_MODE
//#define DEBUG_MODE
#endif
	
struct turtle
{
	string name;
	int index;
};
	
void shell_sort(turtle start[], turtle last[], int capacity)
{
	// 为初始状态的乌龟赋予序号。
	for (int i = 0; i < capacity; i++)
		for (int j = 0; j < capacity; j++)
			if (start[j].name == last[i].name)
			{
				start[j].index = last[i].index;
				break;
			}
	
	// 对初始乌龟状态排序。
	for (int i = capacity; i > 1; i--)
	{
		// 找到序号为i和(i - 1)的两只乌龟在数组的位置。
		int current, previous;
		for (int j = 0; j < capacity; j++)
		{
			if (start[j].index == i)
				current = j;
			if (start[j].index == (i - 1))
				previous = j;
		}
		
		// 如果序号为(i - 1)的乌龟在序号为i的乌龟的下方,则将其放到顶端。
		if (previous > current)
		{
			cout << start[previous].name << endl;
			turtle tmp = start[previous];
			for (int j = previous; j > 0; j--)
			{
				start[j].name = start[j - 1].name;
				start[j].index = start[j - 1].index;
			}
			start[0].name = tmp.name;
			start[0].index = tmp.index;
		}
		
	#ifdef DEBUG_MODE
		cout << "<Debug Begin>" << endl;
		for (int j = 0; j < capacity; j++)
			cout << start[j].index << " " << start[j].name << endl;
		cout << "<Debug End>" << endl;
	#endif
	}
}
	
int main(int ac, char *av[])
{
	int cases, capacity;
	turtle start[MAXSIZE];
	turtle last[MAXSIZE];
	
	cin >> cases;
	while(cases--)
	{
		cin >> capacity;
		cin.ignore();
		
		// 读入初始状态。
		for (int i = 0; i < capacity; i++)
			getline(cin, start[i].name);
		
		// 读入最终状态,并赋予每只乌龟序号。
		for (int i = 0; i < capacity; i++)
		{
			getline(cin, last[i].name);
			last[i].index = (i + 1);
		}
		
		// 开始龟壳排序!
		shell_sort(start, last, capacity);
		
		cout << endl;
	}
	
	return 0;
}

抱歉!评论已关闭.