gotutiyan’s blog

競技プログラミングをやったりopenframeworksでお絵かきをしたりしています。

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;
}