2011-06-14 21:10:27Morris
b255. D. 跑跑卡丁車
內容 ：
你玩過跑跑卡丁車嗎？這是款遊戲橘子代理的線上賽車遊戲，分成道具賽跟競速賽兩種模式，道具賽中可以丟水球、香蕉皮等等來擾亂對手，而競速賽則是純粹的比誰快！ 但你知道卡丁車是真的存在的東西嗎？
卡 丁車是賽車界最初級的賽事，所有有名的車手小時候都是從這項賽事中開始學習的，有名的F1世界冠軍舒馬赫退休後甚至重溫童年時光以參加卡丁車賽事為樂。 可別小看小小的一台車，輕量化的車身加上強力引擎的搭配，能夠輕鬆跑出百公里的時速，刺激度不輸一般賽車，能否良好的駕馭這小怪獸也是對車手的考驗。 國內的卡丁車賽事通常分為測時賽、複賽1、複賽2、決賽四個階段，測時賽不需同時出發，每個車手必須在有限的時間內盡量達到最快的單圈時間，測時賽的排名 決定複賽1的起跑位置，從複賽1開始則都是同時起跑，複賽1的 排名決定複賽2的起跑位置，複賽2的排名決定決賽的起跑位置。 根據研究發現，如果能在測時賽中拿到前1/3的排名，則贏得比賽的機率會大增，身為NPSC車隊技術員的你，找出測時賽前1/3的車手提供給車隊研究吧！ 假設有N個車手，前1/3的定義是排名前(N/3, 無條件捨去)的車手，例外條件是當有未列入前1/3的車手成績與第N/3名的車手成績相同的話，也必須將他算入前1/3
輸入說明
：
測
資會有多組，每組測資的第一行是一個整數N，3<=N<=100000，當N=0的時候表示測資結束，接下來的N行分別是車手的姓名及測時賽
的最佳單圈成績，姓名只會包含大小寫英文字母，成績的格式為HH:MM:SS.SSS(小數點後可能有0到3個位數)，秒數精確到三位數，姓名與成績用一
個空白隔開。
輸出說明
：
對每組測資，請先輸出一行LIST START，接下來輸出符合條件的車手名稱，輸出順序請依照出現在測資的順序，車手輸出完畢後請輸出一行LIST END。
範例輸入 ：
3 Schumacher 00:01:46.532 Alonso 00:01:47.581 DE 00:01:46.531 3 Schumacher 00:01:00 Alonso 00:01:00 DE 00:01:00 0
範例輸出 ：
LIST START DE LIST END LIST START Schumacher Alonso DE LIST END
提示
：
出處
：
2009 NPSC 高中組決賽
作法 : 排序
輸出比較麻煩，照著原本的順序輸出，此時不用考慮它的排名
只要在1/3中即可
作法 : 排序
輸出比較麻煩，照著原本的順序輸出，此時不用考慮它的排名
只要在1/3中即可
/**********************************************************************************/
/* Problem: b255 "D. 跑跑卡丁車" from 2009 NPSC 高中組決賽 */
/* Language: C */
/* Result: AC (168ms, 8296KB) on ZeroJudge */
/* Author: morris1028 at 2011-06-12 11:56:43 */
/**********************************************************************************/
#include<stdio.h>
struct Axis{
double t;
int index;
}Data[100001], X[100001];
void Merge(int l, int m, int h) {
int In1=l, In2=m+1;
int a, b, Top=0;
while(In1<=m && In2<=h)
if(Data[In1].t <= Data[In2].t)
X[Top++] = Data[In1++];
else X[Top++] = Data[In2++];
while(In1<=m) X[Top++] = Data[In1++];
while(In2<=h) X[Top++] = Data[In2++];
for(a=0,b=l;a<Top;a++,b++)
Data[b]=X[a];
}
void MergeSort(int l, int h) {
if(l < h) {
int m=(l+h)/2;
MergeSort(l ,m);
MergeSort(m+1,h);
Merge(l,m,h);
}
}
char name[100000][50];
double time[100000];
main() {
int n, H, M, a;
double S;
while(scanf("%d", &n) == 1 && n) {
for(a = 0; a < n; a++) {
scanf("%s %d:%d:%lf", name[a], &H, &M, &S);
Data[a].t = H*3600.0 + M*60.0 + S, Data[a].index = a;
time[a] = Data[a].t;
}
MergeSort(0, n-1);
int n2 = n/3-1;
puts("LIST START");
for(a = 0; a < n; a++)
if(time[a] <= Data[n2].t)
puts(name[a]);
puts("LIST END");
}
return 0;
}
上一篇：d931. C. 幽靈特務報到