AOJ 0298 Bus Timetable
問題
路線バスの時刻表 | Aizu Online Judge
バスの時刻表の情報が2つ与えられるので、2つの時刻表をまとめて、早い時間から順に出力する。
解法
とりあえずバスの時刻表を1つの配列にまとめて格納する。vectorとかにpush_backしていけば良い。
格納し終わったら、sort()でソートしよう。pairを要素にもつ配列をこの関数でソートするとき、.firstである1番目の要素が優先的にソートされ、これが同じ時は.secondの2番目値でソートされる。つまり、この問題では時間でソートされつつ、同じ時間の時は分で早い順に並ぶことになる。これにより、時間の早い順にすることができる。
次に時間の重複に注意しよう。サンプルケースの2つ目にように、21:00が2個あっても1つだけ出力する。
これには重複を消すためのunique() を利用しよう。
unique(操作をしたい範囲のイテレータ)で使うことができ、重複を消したことにより余った部分の先頭のイテレータが戻り値になる。
例えば、以下のような配列v
1 2 3 3 4 4 5
に対してunique(v.begin(),v.end())を行うと、
1 2 3 4 5 # #
となり、#の部分が余るので、戻り値は前から6番目、v.begin()+5となる。
そして、今度はv.erase(消したい範囲のイテレータ)を利用して、unique()の戻り値とv.end()の範囲を消すことができ、これで余った領域を消すことができる。
最後に、時間は単純に出力、分は0埋め2桁で出力することに注意して完成。
マクロでfirst: fi , second: se , push_back: pbとしています。
int main() { int n,m; vector<pair<int,int>> v; //1つ目の時刻表 cin>>n; rep(i,0,n){ int h,m; cin>>h>>m; v.pb(make_pair(h,m)); } //2つ目の時刻表 cin>>m; rep(i,0,m){ int h,m; cin>>h>>m; v.pb(make_pair(h,m)); } Sort(v); //重複を消す v.erase(unique(v.begin(),v.end()),v.end()); //時間は普通に、分は0埋め2桁で出力。 rep(i,0,v.size()){ if(i)cout<<" "; printf("%d:%02d",v[i].fi,v[i].se); } cout<<endl; return 0; }