首页 > 代码库 > uva10132File Fragmentation(贪心)
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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。