Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.Arrays;
- import java.util.Scanner;
- public class Solution {
- static int gasStations;
- static Long maxFuel;
- static Long startingFuel;
- static Long length;
- private static class Station implements Comparable<Station> {
- long price;
- long pos;
- private Station(long price, long pos) {
- this.price = price;
- this.pos = pos;
- }
- @Override
- public int compareTo(Station o) {
- return Long.valueOf(price).compareTo(o.price);
- }
- @Override
- public String toString() {
- return "{" + price + "$, " + pos + "}";
- }
- }
- public static void main(String[] args) {
- Scanner scanner = new Scanner(System.in);
- int M = Integer.parseInt(scanner.nextLine());
- for (int i = 0; i < M; i++) {
- String[] line = scanner.nextLine().split("\\s+");
- gasStations = Integer.parseInt(line[0]);
- maxFuel = Long.parseLong(line[1]);
- startingFuel = Long.parseLong(line[2]);
- length = Long.parseLong(line[3]);
- Station[] stations = new Station[gasStations];
- for (int s = 0; s < gasStations; s++) {
- line = scanner.nextLine().split("\\s+");
- stations[s] = new Station(Long.parseLong(line[1]), Long.parseLong(line[0]));
- }
- //SORTING STATIONS, CHEAPEST FIRST
- Arrays.sort(stations);
- checkSolution(stations);
- }
- }
- private static void checkSolution(Station[] stations) {
- long[] reserveFuel = {0};
- System.out.println(recursiveCall(0, length, startingFuel, stations, reserveFuel));
- }
- // RETURNS THE $$ SPENT IN FUEL
- // PARAMS:
- // START: the start point of this part of the trip
- // END: the goal of this part of the trip
- // FUEL: the amount of fuel I have for this section
- // STATIONS: all the stations, nulled out the ones I have been to
- // RESERVE FUEL: pointer used to return the amount of gas that was left after the trip. /*I'm not proud of this*/
- private static long recursiveCall(long start, long end, long fuel, Station[] stations, long [] reserveFuel) {
- // System.out.println("RECURSIVING -- start:" + start + " end:" + end + " fuel:" + fuel);
- // IF I HAVE ENOUGH FUEL TO GET TO THE END
- if (end - start <= fuel) {
- reserveFuel[0] = fuel - (end - start);
- return 0; //SPENT NO CASH, I COULD GET THERE WITH THE CURRENT TANK
- }
- Station station = null;
- for (int s = 0; s < gasStations && station == null; s++) {
- // GET THE FIRST (AND CHEAPEST) STATION BETWEEN MY CURRENT START AND END POSITIONS
- if (stations[s] != null && stations[s].pos >= start && stations[s].pos < end) {
- station = stations[s];
- stations[s] = null; //NULLING OUT USED STATIONS
- }
- }
- // THERE ARE NO STATIONS BETWEEN START AND END
- if (station == null) {
- return -1; // CAN'T GET THERE
- }
- long ans = 0; // TOTAL $ SPENT
- long var = recursiveCall(start, station.pos, fuel, stations, reserveFuel);
- // IF I COULDN'T MAKE IT
- if(var == -1)
- return var;
- ans += var; // ADDING THE $$ NEEDED TO GET HERE
- long neededFuel = Math.min(maxFuel- reserveFuel[0], end - station.pos - reserveFuel[0]);
- long chargedFuel = reserveFuel[0] + neededFuel;
- ans += (neededFuel * station.price); // ADDING WHAT I SPENT HERE
- // System.out.println("CHARGING FUEL -- $" + (neededFuel * station.price) + " in:" + station.pos);
- reserveFuel[0] = 0;
- var = recursiveCall(station.pos, end, chargedFuel, stations, reserveFuel);
- // IF I COULDN'T MAKE IT
- if(var == -1)
- return var;
- ans += var; // ADDING WHAT I WILL SPEND IN THE REST OF THE TRIP TO MY GOAL
- return ans;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement