/*
我第一次使用,不知道如何貼程式碼!,有人可以給個指導嗎?
解這題時,有點偷懶想看一下參考,沒找到,解完後就想補完一下
gj:g061 / zj:b255 g061: C.跑跑卡丁車關鍵字: NPSC 2009 國中組決賽
讀入的每筆資料 { 索引 i , 名字 s , 時間串 t }
因為輸入的的時間串 "hh:mm:ss.xxx" 扣掉冒號及小數點,最多 hhmmssxxx最多9位數
將 t 轉成整數 tnum 的方法應可以各顯神通, tnum加上索引i建結構 nt ,
以 vector< nt > vt 存 {i,tnum} , 以 陣列或 vector<string>vs 存對應的名字
將 vt 以自訂比較函式 cmp 來做 sort ,需注意若 tnum相同, 依 i 的順序排
接著,記住前1/3的最後一個在vt的索引k ,然後取出前 1/3 將其在vs的索引值i放入 set<int>out
輸出(1) 依序將 out 內的索引值取出對應vs的名字印出,
(2) 再印出vt[k]之後 tnum值與vt[k]的tnum值相同的名字
*/
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
typedef struct ns { int t,i; } nt;
nt nts;
vector <nt> vt;
vector <string> vs;
bool cmp( nt a , nt b )
{
if(a.t<b.t) return true;
if(a.t>b.t) return false;
return ( a.i < b.i );
}
int main( )
{
int i , j, tnum , n;
string s,t;
while ( cin >> n , n )
{
vs.clear(); vt.clear();
for(i=0; i<n; ++i)
{ //每筆資料 s名字、 t時間串
cin >> s >> t;
vs.push_back(s);
int tlen = t.size();
tnum = (t[0]-48)*100000+(t[1]-48)*10000 + (t[3]-48)*1000+(t[4]-48)*100 + (t[6]-48)*10+t[7]-48;
for(j=9; j<12; ++j) tnum = tnum*10 + (j>tlen ? 0 : t[j]-48 );
nts.t=tnum; nts.i=i;
vt.push_back(nts);
}
sort(vt.begin(), vt.end(), cmp ); // 排序,以自訂比較函式 cmp
cout <<"LIST START" <<endl;
int k=n/3;
// set<out> 存入 前1/3 {依原輸入序} ; 再依序印出
set <int> out;
set <int>::iterator it;
for(i=0; i<k; ++i) out.insert(vt[i].i);
for(it=out.begin(); it != out.end() ; ++it ) cout << vs[ (*it) ] <<endl;
// 補印所有與 最後入圍者 有相同 tnum 者
i=k-1;
while( i<n-1 && vt[i].t == vt[i+1].t )
{
++i; cout << vs[vt[i].i] <<endl;
}
cout <<"LIST END" <<endl;
}
return 0 ;
}