UVa10901FerryLoadingIII

Problem B: Ferry Loading III

There is a ferry across the river that can take ncars across the river in t minutes and return in tminutes. 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

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

#include
#include
#include
#include
#include
using namespace std;
struct load{
int id;
int time;
int ans;
friend bool operator <(load a,load b){
return a.id }
load(int id=0,int time = 0,int ans=-1):id(id),time(time),ans(ans){}
};
vector vl;
queue que[2];
int cap,cost,n;
void init(){
while(!que[1].empty()) que[1].pop();
while(!que[0].empty()) que[0].pop();
vl.clear();
}
int main(){
int ncase;
cin >> ncase;
while(ncase--){
init();
cin >> cap >> cost >> n;
for(int i = 0; i int ti;
string dir;
cin >> ti >> dir;
if(dir=="left")
que[0].push(load(i,ti,-1));
else
que[1].push(load(i,ti,-1));
}
int turn = 0,time = 0;
while(1){
int cnt = 0;
while(que[turn].front().time<=time&&cnt que[turn].front().ans = time+cost;
vl.push_back(que[turn].front());
que[turn].pop();
cnt++;
}
if(que[turn].size()==0&&que[!turn].size()==0) break;
if(cnt==0){
if((que[!turn].size()==0||que[!turn].front().time>que[turn].front().time)&&que[turn].size()){
time = que[turn].front().time;
}else if(que[!turn].size()!=0){
if(que[!turn].front().time>time){
time = que[!turn].front().time+cost;
turn = !turn;
}else{
time += cost;
turn = !turn;
}
}
}else{
time += cost;
turn = !turn;
}
}
sort(vl.begin(),vl.end());
for(int i = 0; i if(ncase)
cout< }
return 0;
}

UVa10901 - Ferry Loading III,布布扣,bubuko.com