b217. 2. 線串式主題閱讀系統
內容 ：
因為網路論壇的流行，吸引大量的內容討論文 章。但傳統的閱讀方式是條列式、依照時間出現順序排列，一旦討論數量龐大，很難找到集中的討論主題。線串主題 (subject threading)就是一種將相同主題 (subject)集中，以方便閱讀的瀏覽方式。我們希望設計線串主題排列系統，挑選集中相同的主題文章，再依照最早出現主題的時間，依序排列。為了簡化 系統，我們將文章的主題與發表時間摘要出來，成為一個集中的索引檔案，請根據此索引檔，輸出線串主題。
文章索引檔表示法說明：
索引檔內為每一篇文章建立三個欄位，分別為主題(Subject)、日期(Date)、與識別碼(ID)。主題表示為：
Subject: xxxxx
其
中“Subject:’’ 之後有一空白，“xxxxx” 為主題內容。主題內容可含除換行之外的任何字元。主題內容前三個字元若為
“Re:”或“RE:”則忽略不計。若內容有多組“Re:”或“RE:”刪除第一組即可，內容字串第一個非空白字元前之任何數量的空白(0x20)皆忽略
不計；而主題字串最後一個非空白字元之後的所有空白字元也忽略不計，除此之外，比較兩主題是否相同時，所有字元必須完全相同，例如以下前三個主題皆視為相
同主題，但最後一個則視為不同的主題：
Subject: 有關高中程式競賽
Subject: Re: 有關高中程式競賽
Subject: Re:有關高中程式競賽
Subject: Re: Re: 有關高中程式競賽
日期欄位表示如右： M D H Y
其
中，M 為 1 至 12 的整數，分別代表 1 月到 12 月。D 為 1 到 31 的整數，表示當月份第 1 日至 31 日。H 表示時，為 0
到 23 的整數。Y 代表年，為四位整數。數字間以一個空白相隔。例如以下日期表示 2008 年 11 月 3 日 12 時：
Date: 11 3 12 2008
“Date:’’ 之後有一空白。
識別碼則以最多十位整數表示 每一篇文章之識別碼在索引檔中都是唯一 例如，。：
ID: 1234567
“ID:’’ 之後有一空白。
輸入說明
：
輸出說明
：
Subject: 有關高中程式競賽
ID: 1234657,123456,98765
Subject: 高中程式競賽地點
ID: 8888,9999,1000
範例輸入 ：
輸入範例 1： Subject: 經濟風暴 Date: 11 20 10 2008 ID: 1 Subject: 美國總統當選人 Date: 11 19 12 2008 ID: 12 Subject: Re: 經濟風暴 Date: 11 21 20 2008 ID: 34 Subject: Re: 美國總統當選人 Date: 11 22 13 2008 5 ID: 98 輸入範例 2： Subject: 失業率升高 Date: 11 28 10 2008 ID: 1 Subject: 美國總統當選人 Date: 11 19 12 2008 ID: 12 Subject: 經濟風暴 Date: 11 21 20 2008 ID: 34 Subject: Re: 美國總統當選人 Date: 11 22 13 2008 ID: 98
範例輸出 ：
輸出範例 1：(只需輸出最早出現的 2 個線串) Subject: 美國總統當選人 ID: 12,98 Subject: 經濟風暴 ID: 1,34 輸出範例 2：(只需輸出最早出現的 2 個線串) Subject: 美國總統當選人 ID: 12,98 Subject: 經濟風暴 ID: 34
提示
：
出處
：
紀錄時間點最早的兩個線串
/**********************************************************************************/
/* Problem: b217 "2. 線串式主題閱讀系統" from 97全國資訊學科能力競賽*/
/* Language: C */
/* Result: AC (7ms, 336KB) on ZeroJudge */
/* Author: morris1028 at 2011-08-26 23:59:37 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct {
char Subject[1025];
int Date[4];
int ID[100], IDl;
int input;
}Article;
Article in[10000];
int cmp(const void *a, const void *b) {
Article *aa, *bb;
aa = (Article *)a, bb = (Article *)b;
if(aa->Date[3] > bb->Date[3]) return 1;
else if(aa->Date[3] < bb->Date[3]) return 0;
else {
if(aa->Date[0] > bb->Date[0]) return 1;
else if(aa->Date[0] < bb->Date[0]) return 0;
else {
if(aa->Date[1] > bb->Date[1]) return 1;
else if(aa->Date[1] < bb->Date[1]) return 0;
else {
if(aa->Date[2] > bb->Date[2]) return 1;
else if(aa->Date[2] < bb->Date[2]) return 0;
else {
return aa->input > bb->input;
}
}
}
}
}
main() {
char Subject[10], Date[10], ID[10], name[1025];
int M, D, H, Y, id, index = 0, a, b, C = 0;
while(scanf("%s", Subject) == 1) {
++C;
getchar(), gets(name);
scanf("%s %d %d %d %d", Date, &M, &D, &H, &Y);
scanf("%s %d", ID, &id);
int i = 0, j = 0, l = strlen(name);
if(name[0] == 'R' && (name[1] == 'E' || name[1] == 'e')&& name[2] == ':')
i = 3;
while(name[i] == ' ') i++;
for(; i < l; i++) name[j++] = name[i];
i = j-1;
while(name[i] == ' ') i--;
name[i+1] = '\0';
for(a = 0; a < index; a++) {
if(!strcmp(in[a].Subject, name)) {
in[a].ID[in[a].IDl++] = id;
break;
}
}
if(a == index) {
for(b = 0; name[b]; b++)
in[a].Subject[b] = name[b];
in[a].Subject[b] = '\0';
in[a].Date[0] = M, in[a].Date[1] = D, in[a].Date[2] = H, in[a].Date[3] = Y;
in[a].IDl = 0, in[a].ID[in[a].IDl++] = id;
in[a].input = C;
index++;
if(index > 3) {
for(b = 0; b < index-1; b++)
if(cmp(&in[b], &in[index-1]) == 1) {
break;
}
if(b != index-1)
in[b] = in[index-1];
index--;
}
}
}
qsort(in, index, sizeof(Article), cmp);
for(a = 0; a < 2; a++) {
printf("Subject: %s\nID: ", in[a].Subject);
for(b = 0; b < in[a].IDl; b++)
if(b == 0) printf("%d", in[a].ID[b]);
else printf(",%d", in[a].ID[b]);
puts("");
}
return 0;
}
上一篇：b177. 山景 Skyline
下一篇：b180. 1. 遊園接駁車