SHOW:
|
|
- or go back to the newest paste.
| 1 | ||
| 2 | import java.util.Arrays; | |
| 3 | import java.util.Scanner; | |
| 4 | ||
| 5 | public class Solution {
| |
| 6 | static int gasStations; | |
| 7 | static Long maxFuel; | |
| 8 | static Long startingFuel; | |
| 9 | static Long length; | |
| 10 | ||
| 11 | private static class Station implements Comparable<Station> {
| |
| 12 | long price; | |
| 13 | long pos; | |
| 14 | ||
| 15 | private Station(long price, long pos) {
| |
| 16 | this.price = price; | |
| 17 | this.pos = pos; | |
| 18 | } | |
| 19 | ||
| 20 | @Override | |
| 21 | public int compareTo(Station o) {
| |
| 22 | return Long.valueOf(price).compareTo(o.price); | |
| 23 | } | |
| 24 | ||
| 25 | @Override | |
| 26 | public String toString() {
| |
| 27 | return "{" + price + "$, " + pos + "}";
| |
| 28 | } | |
| 29 | } | |
| 30 | ||
| 31 | public static void main(String[] args) {
| |
| 32 | Scanner scanner = new Scanner(System.in); | |
| 33 | int M = Integer.parseInt(scanner.nextLine()); | |
| 34 | for (int i = 0; i < M; i++) {
| |
| 35 | String[] line = scanner.nextLine().split("\\s+");
| |
| 36 | gasStations = Integer.parseInt(line[0]); | |
| 37 | maxFuel = Long.parseLong(line[1]); | |
| 38 | startingFuel = Long.parseLong(line[2]); | |
| 39 | length = Long.parseLong(line[3]); | |
| 40 | Station[] stations = new Station[gasStations]; | |
| 41 | for (int s = 0; s < gasStations; s++) {
| |
| 42 | line = scanner.nextLine().split("\\s+");
| |
| 43 | stations[s] = new Station(Long.parseLong(line[1]), Long.parseLong(line[0])); | |
| 44 | } | |
| 45 | //SORTING STATIONS, CHEAPEST FIRST | |
| 46 | Arrays.sort(stations); | |
| 47 | checkSolution(stations); | |
| 48 | } | |
| 49 | ||
| 50 | } | |
| 51 | ||
| 52 | private static void checkSolution(Station[] stations) {
| |
| 53 | long[] reserveFuel = {0};
| |
| 54 | System.out.println(recursiveCall(0, length, startingFuel, stations, reserveFuel)); | |
| 55 | } | |
| 56 | ||
| 57 | // RETURNS THE $$ SPENT IN FUEL | |
| 58 | - | // RETURNS THE $$ SPENT IN FUEL |
| 58 | + | // PARAMS: |
| 59 | // START: the start point of this part of the trip | |
| 60 | // END: the goal of this part of the trip | |
| 61 | - | // IF I HAVE ENOUGH FUEL TO GET TO THE END |
| 61 | + | // FUEL: the amount of fuel I have for this section |
| 62 | // STATIONS: all the stations, nulled out the ones I have been to | |
| 63 | // RESERVE FUEL: pointer used to return the amount of gas that was left after the trip. /*I'm not proud of this*/ | |
| 64 | private static long recursiveCall(long start, long end, long fuel, Station[] stations, long [] reserveFuel) {
| |
| 65 | // System.out.println("RECURSIVING -- start:" + start + " end:" + end + " fuel:" + fuel);
| |
| 66 | // IF I HAVE ENOUGH FUEL TO GET TO THE END | |
| 67 | if (end - start <= fuel) {
| |
| 68 | reserveFuel[0] = fuel - (end - start); | |
| 69 | - | // GET THE FIRST (AND CHEAPEST) STATION BETWEEN MY CURRENT START AND END POSITIONS |
| 69 | + | |
| 70 | } | |
| 71 | ||
| 72 | Station station = null; | |
| 73 | for (int s = 0; s < gasStations && station == null; s++) {
| |
| 74 | // GET THE FIRST (AND CHEAPEST) STATION BETWEEN MY CURRENT START AND END POSITIONS | |
| 75 | - | // THERE ARE NO STATIONS BETWEEN START AND END |
| 75 | + | |
| 76 | station = stations[s]; | |
| 77 | stations[s] = null; //NULLING OUT USED STATIONS | |
| 78 | } | |
| 79 | } | |
| 80 | // THERE ARE NO STATIONS BETWEEN START AND END | |
| 81 | - | long var = recursiveCall(start, station.pos, fuel, stations, reserveFuel); |
| 81 | + | |
| 82 | - | // IF I COULDN'T MAKE IT |
| 82 | + | |
| 83 | } | |
| 84 | long ans = 0; // TOTAL $ SPENT | |
| 85 | ||
| 86 | - | ans += var; // ADDING THE $$ NEEDED TO GET HERE |
| 86 | + | long var = recursiveCall(start, station.pos, fuel, stations, reserveFuel); |
| 87 | // IF I COULDN'T MAKE IT | |
| 88 | - | long neededFuel = Math.min(maxFuel- reserveFuel[0], end - station.pos - reserveFuel[0]); |
| 88 | + | |
| 89 | return var; | |
| 90 | - | long chargedFuel = reserveFuel[0] + neededFuel; |
| 90 | + | |
| 91 | ans += var; // ADDING THE $$ NEEDED TO GET HERE | |
| 92 | ||
| 93 | long neededFuel = Math.min(maxFuel- reserveFuel[0], end - station.pos - reserveFuel[0]); | |
| 94 | ||
| 95 | long chargedFuel = reserveFuel[0] + neededFuel; | |
| 96 | - | // IF I COULDN'T MAKE IT |
| 96 | + | |
| 97 | ||
| 98 | // System.out.println("CHARGING FUEL -- $" + (neededFuel * station.price) + " in:" + station.pos);
| |
| 99 | reserveFuel[0] = 0; | |
| 100 | - | ans += var; // ADDING WHAT I WILL SPEND IN THE REST OF THE TRIP TO MY GOAL |
| 100 | + | |
| 101 | // IF I COULDN'T MAKE IT | |
| 102 | if(var == -1) | |
| 103 | return var; | |
| 104 | ||
| 105 | ans += var; // ADDING WHAT I WILL SPEND IN THE REST OF THE TRIP TO MY GOAL | |
| 106 | return ans; | |
| 107 | } | |
| 108 | } |