Problem Solving►UVa

UVa 10901 - Ferry Loading III

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

題目網址

幾個關鍵的地方：

The ferry travels continuously back and forth between the banks so long it is carrying a car
or there is at least one car waiting at either bank.

If there are no cars waiting on either bank, the ferry waits
until one arrives, loads it (if it arrives on the same bank of the ferry), and crosses the river.

Solution

注意要有其中一邊車在等，船才會動。

如果船在的另一邊已經有車在等了，那船的這邊一載完已經到的後就要馬上開走。
有可能空船走，但前提是另一邊要有車在等。

Code

UVa 10901
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <cstdio>
#include <queue>
#define N 10000

int main()
{
    struct car
    {
        int id, arr_time;
        car() {}
        car(int id_, int arr_) : id(id_), arr_time(arr_) {}
    };

    int tar_time[N]; //到達目的時間
    int Case;
    scanf("%d", &Case);
    while (Case--)
    {
        int n, t, m;
        scanf("%d%d%d", &n, &t, &m);

        std::queue<car> bank[2]; //0: left, 1: right

        char str[6];
        int tmp;
        for (int i = 0; i < m; ++i)
        {
            scanf("%d%s", &tmp, str);
            if (str[0] == 'l')
                bank[0].emplace(i, tmp);
            else
                bank[1].emplace(i, tmp);
        }

        int now = 0, load = 0;
        int tt = 0;
        int side = 0, opposite = 1; //0: left, 1: right

        car c;
        //要注意其中一邊有車或船上有車時，船才會動
        while (!bank[0].empty() || !bank[1].empty())
        {
            tt = now + t; //該趟到達對岸的時間

            if (bank[side].empty())
            {
                //空船開到另一邊
                if (now < bank[opposite].front().arr_time)
                    tt = bank[opposite].front().arr_time + t;
            }
            else
            {
                //first car
                c = bank[side].front();
                if (c.arr_time > now)
                {
                    //另一邊沒有車了 或 另一邊的到達時間比這邊的慢，就停原地等
                    if (bank[opposite].empty() || bank[opposite].front().arr_time >= c.arr_time)
                    {
                        now = c.arr_time;
                        tt = now + t;
                    }
                    else
                    {
                        //空船開到另一邊
                        if (now < bank[opposite].front().arr_time)
                            now = bank[opposite].front().arr_time + t; //另一邊沒車，等車到了船才會開過去
                        else
                            now = tt; //另一邊有車，直接開過去

                        opposite = side;
                        side ^= 1;
                        continue;
                    }
                }

                load = 1;
                tar_time[c.id] = tt;
                bank[side].pop();

                //other cars
                while (load < n && !bank[side].empty())
                {
                    c = bank[side].front();

                    if (c.arr_time > now) //這邊到的載完了，直接開到對岸
                        break;

                    ++load;
                    tar_time[c.id] = tt;
                    bank[side].pop();
                }
            }

            load = 0;
            now = tt;
            opposite = side;
            side ^= 1;
        }

        for (int i = 0; i < m; ++i)
            printf("%d\n", tar_time[i]);

        if (Case)
            putchar('\n');
    }

    return 0;
}