本文主要是介绍uva10132File Fragmentation（贪心），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：uva10132File Fragmentation
题目大意：有n个文件，都是相同的，但是不小心打破了，而且每个文件的裂痕不一样，每个文件都损坏成两个碎片。每个文件的碎片都用2进制数表示，然后给出2*n个碎片，问这样的碎片能得到的文件（n个）。如果答案不唯一，给出其中一个就可以。
解题思路：因为每两个碎片形成一个文件，那么找出最长的碎片，那么它必然和最小的文件匹配组成文件。每种情况都尝试一下，并且组成文件后需要验证一下是否剩余的碎片可以组成这个文件。
这题的输入要注意一下，因为它是以空格来隔开两个输入的样例。
代码：
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;const int N = 300;
const int M = 150;
int n, sum;
char ans[N];
int vis[M];struct Fragment {char str[N];int len;
}f[M];int cmp (const Fragment & a, const Fragment &b) {return a.len > b.len;
}bool judge (int a, int b) {memset(vis, 0, sizeof(vis));vis[a] = vis[b] = 1;char temp[N];for (int i = 0; i < n; i++) {if (vis[i])continue;vis[i] = 1;int j;for (j = i + 1; j < n; j++) {if (vis[j])continue;if (f[i].len + f[j].len == sum) {strcpy (temp, f[i].str);strcat (temp, f[j].str);if (strcmp (temp, ans) == 0) {vis[j] = 1;break;}strcpy (temp, f[j].str);strcat (temp, f[i].str);if (strcmp (temp, ans) == 0) {vis[j] = 1;break;}}}if (j == n)return 0;}return 1;
}void solve () {int max = f[0].len;int min;for (int i = 0; i < n; i++)if (f[i].len == sum - max) {min = i;break;}for (int i = 0; i < n; i++) {if (f[i].len != max)return;for (int j = min; j < n; j++) {if (f[j].len != f[min].len)break;strcpy (ans, f[i].str);strcat (ans, f[j].str);if (judge (i, j))return;strcpy (ans, f[j].str);strcat (ans, f[i].str);if (judge (i, j))return;}}
}int main () {int t;char ch;scanf ("%d%*c", &t);getchar();while (t--) {n = sum = 0;while (gets(f[n].str) != NULL) {f[n].len = strlen (f[n].str);sum += f[n].len;if (strcmp(f[n].str,"") == 0)break;n++;}sum = sum * 2 / n;//printf ("%d %d\n", sum, n);sort (f, f + n, cmp);
/* for (int i = 0; i < n; i++)printf ("%s\n", f[i].str);*/solve();printf ("%s\n", ans);if (t)printf ("\n");}return 0;
}这篇关于uva10132File Fragmentation（贪心）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
