把字典的字母轉成數字並做排序,
出現Q或Z不做轉換。
再把輸入檔的數字,
從字典檔裡做match,
找到就可以output。
本來想用qsort,但是數字相同時,
qsory會重排,所以只好自己寫個sort。
不過這種方法好笨啊!
寫完看到它的分析才知道,
反過來做比較快!
直接從輸入檔的數字,
跟字典的字母做比較,
比較時才把字母轉成數字,
發現沒match,就再找下一個字母,
直到找到為止。
不過這兩種方法有好有壞……
像我就是一次先弄完,之後輸入的數字就可以直接找。
它的作法是每次都從字典的開頭往後找。
不過這題,因為輸入檔只有一筆數字,
所以用它的方法滿不錯的。
資料多筆的話就未必囉!
這大概是USACO跟UVA最大差異,
測資的處理方式不同。
/* ID: mythnc2 LANG: C TASK: namenum Name That Number 2011/11/07 21:10:16 */ #include <stdio.h> #include <stdlib.h> #include <string.h> #define MAXN 5000 #define MAXCHAR 12 #define TRUE 1 #define FALSE 0 typedef struct name { long long number; char name[MAXCHAR]; } Name; int screen(char *); void copy(Name *, char *); void sort(Name *, int); int cton(char); int find(long long, Name *, int); void printout(FILE *, int, Name *, int); int main (void) { FILE *fin, *fout, *fdict; char str[MAXCHAR + 1]; Name cow[MAXN]; int count, index; long long serial; fin = fopen("namenum.in", "r"); fout = fopen("namenum.out", "w"); fdict = fopen("dict.txt", "r"); count = 0; while (fscanf(fdict, "%s", str) != EOF) { if (screen(str)) continue; copy(&cow[count++], str); sort(cow, count); } fscanf(fin, "%lld", &serial); if ((index = find(serial, cow, count)) > -1) printout(fout, index, cow, count); else fprintf(fout, "NONE\n"); return 0; } /* screen: if letter has Q or Z, * jump over it */ int screen(char *s) { for (; *s != '\0'; s++) if (*s == 'Q' || *s == 'Z') return TRUE; return FALSE; } /* copy: copy the letter and number of s * to cow */ void copy(Name *cow, char *s) { int i; /* copy letters */ strcpy(cow->name, s); /* make letter to number */ for (cow->number = i = 0; s[i] != '\0'; i++) { if (i > 0) cow->number *= 10; cow->number += cton(s[i]); } } /* sort: insertion sort array cow */ void sort(Name *cow, int n) { int i; Name tmp; if (n < 2) return; tmp = cow[n - 1]; for (i = n - 2; i > -1; i--) if (cow[i].number > tmp.number) { cow[i + 1] = cow[i]; if (i == 0) cow[i] = tmp; } else { cow[i + 1] = tmp; break; } } /* cton: cast char to number */ int cton(char c) { char letter[24] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y'}; int i; for (i = 0; i < 24; i++) if (c == letter[i]) return 2 + i / 3; } /* find: find number in array cow * if find return index, * else return -1 */ int find(long long number, Name *cow, int n) { int head, mid, tail; head = 0; tail = n - 1; while (head <= tail) { mid = (head + tail) / 2; if (cow[mid].number < number) head = mid + 1; else if (cow[mid].number > number) tail = mid - 1; else return mid; } return -1; } /* printout: print out result */ void printout(FILE *f, int i, Name *cow, int n) { /* find the first same value number */ while (cow[i - 1].number == cow[i].number && i - 1 >= 0) i--; /* print out */ fprintf(f, "%s\n", cow[i].name); while (cow[i + 1].number == cow[i].number && i + 1 < n) { i++; fprintf(f, "%s\n", cow[i].name); } }
沒有留言:
張貼留言