[UVA][Queue] 10901 - Ferry Loading III
Problem B: Ferry Loading III
Before bridges were common, ferries were used to transport cars across rivers. River ferries, unlike their larger cousins, run on a guide line and are powered by the river's current. Cars drive onto the ferry from one end, the ferry crosses the river, and the cars exit from the other end of the ferry.There is a ferry across the river that can take n cars across the river in t minutes and return in t minutes. A car may arrive at either river bank to be transported by the ferry to the opposite bank. 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. Whenever the ferry arrives at one of the banks, it unloads its cargo and loads up to n cars that are waiting to cross. If there are more than n, those that have been waiting the longest are loaded. 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. At what time does each car reach the other side of the river?
The first line of input contains c, the number of test cases. Each test case begins with n, t, m. m lines follow, each giving the arrival time for a car (in minutes since the beginning of the day), and the bank at which the car arrives ("left" or "right"). For each test case, output one line per car, in the same order as the input, giving the time at which that car is unloaded at the opposite bank. Output an empty line between cases.
You may assume that 0 < n, t, m ≤ 10000. The arrival times for each test case are strictly increasing. The ferry is initially on the left bank. Loading and unloading time may be considered to be 0.
Sample input
2 2 10 10 0 left 10 left 20 left 30 left 40 left 50 left 60 left 70 left 80 left 90 left 2 10 3 10 right 25 left 40 left
Output for sample input
10 30 30 50 50 70 70 90 90 110 30 40 60
Gordon V. Cormack
描述一下題目內容
渡船一開始在左側，
根據時間，車子依序抵達。
如果兩邊都沒有車子，渡船就會在那一側持續等待。
然而，如果一邊有車子，而渡船那一側還沒有車子，渡船則會開到另一邊去載。
如果渡船抵達後，有可以載的車子，最多載 N 輛，便立刻出發到另一岸。
結果 ... 代碼被我寫醜了，因為我看不太懂題目。
#include <stdio.h>
#include <queue>
#include <algorithm>
using namespace std;
struct car {
int t, in;
car(int x, int y) {
t = x;
in = y;
}
};
int main() {
int testcase, n, m, t, i;
scanf("%d", &testcase);
while(testcase--) {
scanf("%d %d %d", &n, &t, &m);
int time;
char s[50];
queue<car> LEFT, RIGHT;
for(i = 0; i < m; i++) {
scanf("%d %s", &time, s);
if(s[0] == 'l')
LEFT.push(car(time, i));
else
RIGHT.push(car(time, i));
}
int now_time = 0, flag = 0;
int res[10000];
while(1) {
if(LEFT.empty() && RIGHT.empty())
break;
//printf("time %d : %s\n", now_time, flag ? "right" : "left");
int tn = 0;
if(flag == 0) { // LEFT bank
while(tn < n && !LEFT.empty() && LEFT.front().t <= now_time)
tn++, res[LEFT.front().in] = now_time+t, LEFT.pop();
if(tn) { // goto either
now_time += t;
flag = 1-flag;
continue;
}
if(RIGHT.empty() || (!LEFT.empty() && LEFT.front().t <= RIGHT.front().t)) {
now_time = LEFT.front().t;// waiting left
while(tn < n && !LEFT.empty() && LEFT.front().t <= now_time)
tn++, res[LEFT.front().in] = now_time+t, LEFT.pop();
now_time += t;
} else {
if(!RIGHT.empty() || LEFT.empty() && LEFT.front().t > RIGHT.front().t)
now_time = max(RIGHT.front().t, now_time)+t;//max tricky
else
now_time += t;
}
} else {
while(tn < n && !RIGHT.empty() && RIGHT.front().t <= now_time)
tn++, res[RIGHT.front().in] = now_time+t, RIGHT.pop();
if(tn) {
now_time += t;
flag = 1-flag;
continue;
}
if(LEFT.empty() || (!RIGHT.empty() && LEFT.front().t >= RIGHT.front().t)) {
now_time = RIGHT.front().t;
while(tn < n && !RIGHT.empty() && RIGHT.front().t <= now_time)
tn++, res[RIGHT.front().in] = now_time+t, RIGHT.pop();
now_time += t;
} else {
if(!LEFT.empty() || RIGHT.empty() && LEFT.front().t < RIGHT.front().t)
now_time = max(LEFT.front().t, now_time)+t;
else
now_time += t;
}
}
flag = 1-flag;
}
for(i = 0; i < m; i++)
printf("%d\n", res[i]);
if(testcase)
puts("");
}
return 0;
}
/*
1
1113 1072 11
8631 left
12526 left
15884 left
19388 left
24635 left
30627 right
30627 left
31757 left
35635 right
36133 left
40444 left
*/