Algoogle

Algorithm for Programming Contest

AOJ 1297 Swimming Jam

Category: AOJ Tag: data-structure, queue

Swimming Jam

問題概要


プールに行きのレーンと帰りのレーンがある.
それぞれの人が決まった速さで決まった回数往復する.
ただし各レーンで追い越しは禁止されていてレーンの端でのみ順番が入れ替えられる.
最後1人が泳ぎ終わる時刻を求めよ.

解法


各レーンをqueueに見立ててやれば, 先頭が到着した時その時刻以前に到着する予定だった人すべてを同時に処理して反対のレーンのqueueに入れてやれば良い.

コード


(1297.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i,a) repi(i,0,a)
#define all(u) begin(u),end(u)
#define pb push_back
struct swimmer{
    int t, res, v;
    bool operator<(const swimmer &s)const{ return v < s.v;}
};
int N, a, b;

int solve(){
    queue<swimmer> que[2];
    rep(i,N){
        cin >> a >> b;
        que[0].push((swimmer){0,b,a});
    }
    int ans = 0;
    while(!que[0].empty() or !que[1].empty()){
        int f = que[0].empty() or (!que[1].empty() and que[1].front().t < que[0].front().t);
        ans = que[f].front().t;
        vector<swimmer> s;
        while(!que[f].empty() and que[f].front().t <= ans){
            s.pb(que[f].front()); que[f].pop();
        }
        sort(all(s));
        rep(i,s.size()) if(s[i].res)
            que[f^1].push((swimmer){ans+s[i].v, s[i].res-f, s[i].v});
    }
    return ans;
}

signed main(){
    while(cin >> N, N)
        cout << solve() << endl;
    return 0;
}

Comments