uva - 10132 - File Fragmentation（贪心）

题意：一堆文件，所有文件都是同样的内容——一串由0和1组成的字串。不小心全部撕成了两份，撕裂的位置都不同，根据这些碎片还原出那个字符串。

方法：把所有的碎片按照长度排序，最短必定对应最长。因为有可能撕成相等长度的两份，所以取最短的两个和最长的两个。枚举所有组合，一样则输出。

注意：输入有点难搞，输入的时候样例之间有空行，根据这个划分样例，最后一个根据EOF。

#include <iostream>  
#include <iomanip>  
#include <string>  
#include <cstring>  
#include <cstdio>  
#include <queue>  
#include <stack>  
#include <algorithm>  
#include <cmath>  

using namespace std;

#define MAX 300

struct File
{
	char s[MAX];
	int len;
};

int num;
File file[MAX];

void Input()
{
	int i = 0;
	char temp[MAX];
	while (true)
	{
		if (gets(temp) == NULL || strlen(temp) == 0)
			break;
		strcpy(file[i].s, temp), file[i].len = strlen(temp);
		i++;
		num++;
	}
}

int cmp(const void *a, const void *b)
{
	return (*(File *)a).len - (*(File *)b).len;
}

int Judge(File a, File b, File c, File d)
{
	char temp_1[MAX], temp_2[MAX];
	strcpy(temp_1, a.s), strcat(temp_1, b.s);
	strcpy(temp_2, c.s), strcat(temp_2, d.s);
	if (!strcmp(temp_1, temp_2))
	{
		puts(temp_1);
		return 1;
	}
	else
		return 0;
}

void Connect()
{
	if (Judge(file[0], file[num-2], file[1], file[num-1]))	return;
	else if (Judge(file[0], file[num-2], file[num-1], file[1]))	return;	
	else if (Judge(file[num-2], file[0], file[1], file[num-1]))	return;
	else if (Judge(file[num-2], file[0], file[num-1], file[1]))	return;
	else if (Judge(file[0], file[num-1], file[1], file[num-2]))	return;
	else if (Judge(file[0], file[num-1], file[num-2], file[1]))	return;
	else if (Judge(file[num-1], file[0], file[1], file[num-2]))	return;
	else if (Judge(file[num-1], file[0], file[num-2], file[1]))	return;
}

int main()
{
#ifdef Local  
	freopen("a.in", "r", stdin);  
#endif  
	int t = 0;
	cin >> t;
	getchar(), getchar();
	while (t--)
	{
		memset(file, 0, sizeof(file));
		num = 0;
		Input();
		qsort(file, num, sizeof(file[0]), cmp);
		Connect();
		if (t)
			cout << endl;
	}
}

uva - 10132 - File Fragmentation（贪心）

原文：http://blog.csdn.net/u013545222/article/details/19083583