[PAT-A] 1033 To Fill or Not to Fill

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        double tank = sc.nextDouble(), distance = sc.nextDouble(), avgDist = sc.nextDouble();
        int n = sc.nextInt();
        List<Station> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(new Station(sc.nextDouble(), sc.nextInt()));
        }
        sc.close();

        Collections.sort(list);
        if (distance == 0) {
            System.out.println("0.00");
            return;
        }
        if (list.get(0).getDist() != 0) {
            System.out.println("The maximum travel distance = 0.00");
            return;
        }

        int curStNum = 0;
        double curGas = 0;
        double curCost = 0;
        double maxDis = tank * avgDist;
        while (true) {
            boolean tag = false;
            boolean isCheaper = false;
            double cheapestPrice = Double.MAX_VALUE;
            int cheapestNum = 0;
            for (int i = curStNum + 1; i <= n; i++) {
                if (i == n || (list.get(i).getDist() - list.get(curStNum).getDist()) > maxDis) break;
                tag = true;
                if (list.get(i).getPrice() < list.get(curStNum).getPrice()) {
                    isCheaper = true;
                    double dist = list.get(i).getDist() - list.get(curStNum).getDist();
                    double needGas = dist / avgDist - curGas;
                    curGas = 0;
                    curCost += needGas * list.get(curStNum).getPrice();
                    curStNum = i;
                    break;
                }
                if (list.get(i).getPrice() < cheapestPrice) {
                    cheapestPrice = list.get(i).getPrice();
                    cheapestNum = i;
                }
            }

            if (!isCheaper && (distance - list.get(curStNum).getDist() <= maxDis)) {
                double dist = distance - list.get(curStNum).getDist();
                double needGas = dist / avgDist - curGas;
                curCost += needGas * list.get(curStNum).getPrice();
                System.out.printf("%.2f", curCost);
                return;
            }

            if (tag && !isCheaper) {
                double needGas = tank - curGas;
                curCost += (needGas * list.get(curStNum).getPrice());
                double dist = list.get(cheapestNum).getDist() - list.get(curStNum).getDist();
                curGas = tank - dist / avgDist;
                curStNum = cheapestNum;
            } else if (!tag) {
                System.out.print("The maximum travel distance = ");
                System.out.printf("%.2f", list.get(curStNum).getDist() + maxDis);
                return;
            }
        }
    }

    static class Station implements Comparable<Station> {
        private final double price;
        private final double dist;

        public Station(double price, double dist) {
            this.price = price;
            this.dist = dist;
        }

        @Override
        public int compareTo(Station s1) {
            return Double.compare(this.dist, s1.getDist());
        }

        public double getPrice() {
            return price;
        }

        public double getDist() {
            return dist;
        }
    }
}

C++

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510;

int c_max, d, d_avg, n;

struct Station {
    double p, d;

    bool operator<(const Station &t) const {
        return d < t.d;
    }
} s[N];

int main() {
    cin >> c_max >> d >> d_avg >> n;
    for (int i = 0; i < n; ++i) cin >> s[i].p >> s[i].d;
    s[n] = {0, (double) d};

    sort(s, s + n + 1);

    if (s[0].d) {
        printf("The maximum travel distance = 0.00\n");
        return 0;
    }

    double res = 0, oil = 0;
    for (int i = 0; i < n;) {
        int k = -1;
        for (int j = i + 1; j <= n && s[j].d - s[i].d <= c_max * d_avg; ++j)
            if (s[j].p < s[i].p) {
                k = j;
                break;
            } else if (k == -1 || s[j].p < s[k].p) k = j;

        if (k == -1) {
            printf("The maximum travel distance = %.2lf\n", s[i].d + (double) c_max * d_avg);
            return 0;
        }

        if (s[k].p <= s[i].p) {
            res += ((s[k].d - s[i].d) / d_avg - oil) * s[i].p;
            oil = 0;
            i = k;
        } else {
            res += (c_max - oil) * s[i].p;
            oil = c_max - (s[k].d - s[i].d) / d_avg;
            i = k;
        }
    }

    printf("%.2lf\n", res);

    return 0;
}