(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
 This problem has been solved by Mfv2.

 Sorter: Uncategorized Waterloo local 2003.01.25 http://acm.pku.edu.cn/JudgeOnline/problem?id=2336

Ferry Loading II is problem number 2336 on the Peking University ACM site.

## Algorithm

This problem uses a simple greedy algorithm to get the all the cars over. We know that we want the last ferry to be run at full capacity to ensure the minimum time possible. Therefore, the first ferry should be run with the [total cars]%[capacity] (or at capacity if [total cars]%[capacity] == 0), and every subsequent run at full capacity. We then need only to fill in the code for minor details for calculating the total time and we have an acceptable solution.

## Solution

This is ugly contest code, please feel free to clean up the solution to make it easier to understand!

```/**********************************************
* Note: this is BAD quality contest code
* mfv2 - 2007-09-10
*********************************************/

import java.util.*;

public class Main {
static int capacity = 0;
static int tripTime = 0;
static int curTime = 0;
static int totalCars = 0;
static int[] arrivals;
static int curCar = 0;
static int trips = 0;
static Scanner sc;

public static void main(String[] args) {
sc = new Scanner(System.in);
int cases = sc.nextInt();
while(cases-- > 0) {
curTime = 0;
curCar = 0;
capacity = sc.nextInt();
tripTime = sc.nextInt();
arrivals = new int[sc.nextInt()];
totalCars = arrivals.length;
trips = 0;
doStuff();
}
}

static void doStuff() {
for (int i = 0; i < arrivals.length; i++) {
arrivals[i] = sc.nextInt();
}
//take first total%capacty cars or capacity
curCar = (totalCars % capacity == 0) ? capacity : totalCars%capacity;
curTime += tripTime + arrivals[curCar - 1];
trips++;
if (curCar == totalCars) {
System.out.println(curTime + " " + trips);
return;
}
curTime += tripTime; //return trip is added AFTER checking if all cars moved over

//take next capacity cars, repeat.
while(curCar < totalCars) {
curCar += capacity;
if (arrivals[curCar - 1] >= curTime) {
curTime += (arrivals[curCar - 1]-curTime);
}
curTime += tripTime;
trips++;
if (curCar == totalCars) {
System.out.println(curTime + " " + trips);
return;
}
curTime += tripTime;
}
}

}
```