To Fill or Not to Fill
题目描述
With highways available, driving a car from Hangzhou to any other city is easy. But since the tank capacity of a car is limited, we have to find gas stations on the way from time to time. Different gas station may give different price. You are asked to carefully design the cheapest route to go.
Input Specification:
Each input file contains one test case. For each case, the first line contains 4 positive numbers: Cmax (<= 100), the maximum capacity of the tank; D (<=30000), the distance between Hangzhou and the destination city; Davg (<=20), the average distance per unit gas that the car can run; and N (<= 500), the total number of gas stations. Then N lines follow, each contains a pair of non-negative numbers: Pi, the unit gas price, and Di (<=D), the distance between this station and Hangzhou, for i=1,…N. All the numbers in a line are separated by a space.
Output Specification:
For each test case, print the cheapest price in a line, accurate up to 2 decimal places. It is assumed that the tank is empty at the beginning. If it is impossible to reach the destination, print “The maximum travel distance = X” where X is the maximum possible distance the car can run, accurate up to 2 decimal places.
Sample Input 1:
50 1300 12 8
6.00 1250
7.00 600
7.00 150
7.10 0
7.20 200
7.50 400
7.30 1000
6.85 300
Sample Output 1:
749.17
Sample Input 2:
50 1300 12 2
7.10 0
7.00 600
Sample Output 2:
The maximum travel distance = 1200.00
- 原题链接
题目分析
- 这道题和leetcode上的gas station感觉莫名的像，回头看了下，思路的确有点相同，但是毕竟PAT，难度真的大很多！我想考场上碰到这样的题我肯定是放弃的了。看了别人的一些博客，还是把代码自己实现了一遍如下：
- cmax是邮箱的最大容积，dis是目的地距离，davg是每单位体积汽油能跑的距离，N的所有加油站数量，不妨假设终点也有个加油站，距离为dis，汽油价格为0.0，按照距离依次将所有加油站排下序，如果最小的距离不是0，直接到不了，如果目的地就是出发点，也算到达了。
- 设置nowprice为当前位置的油价，初始为第一个站点的油价，maxdis的值是当前站点加满油能跑到的最大距离（如果位于100，则可到达100+600=700位置），totalprice是即时计算的所花费的总油费，leftdis是在当前站点加满油跑到下一个加油站点后不加油还可以跑的距离（其实leftdis一般都是0，不是0的情况只在后续站点中找不到比当前站点更便宜的价格时，才在当前站点加满油，所以跑到下个站点还有油剩，这个剩余的油还能跑的距离即为leftdis）；
- 只要当前位置还未到达终点，每次都从当前位置往前加满油所能到达的最大距离这一段距离找，如果找到一个油价更少的，直接加刚好能到达该加油站的油量即可，并更新总油费，注意可能有油剩余；如果没找到比当前站点更便宜的油价，只需要找比当前站点油价贵最少的加油站，找到之后，在当前站点把油加满！为什么？因为反正到了那里也要加油，为什么不趁着当前站点油价便宜多加一些呢？并且加满之后，更新leftdis，nowprice，和totalprice，nowdis等；
- 如果找不到一个加油点，直接在当前站点加满油把，能跑到最大距离易知了；
代码实现：
package PAT;import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;public class Main {
public static void main(String[] args) throws IOException {Read.init(System.in);double cmax = Read.nextDouble(), dis = Read.nextDouble(), davg = Read.nextDouble();int N = Read.nextInt();Station[] list = new Station[N+1];list[0] = new Station(0.0, dis);for (int i=1; i<=N; i++)list[i] = new Station(Read.nextDouble(), Read.nextDouble());Arrays.sort(list);double nowdis = 0, maxdis = 0.0, nowprice = 0.0, totalprice = 0.0, leftdis = 0.0;if (list[0].dis != 0) {System.out.println("The maximum travel distance = 0.00");return;} else nowprice = list[0].price;while (nowdis < dis) {maxdis = nowdis + cmax * davg;double minpricedis = 0, minprice = Integer.MAX_VALUE;int flag = 0;for (int i=1; i<=N && list[i].dis <= maxdis; i++) {if (list[i].dis <= nowdis) continue;if (list[i].price < nowprice) {totalprice += (list[i].dis - nowdis - leftdis) * nowprice / davg;leftdis = 0.0;nowprice = list[i].price;nowdis = list[i].dis;flag = 1;break;}if (list[i].price < minprice) {minprice = list[i].price;minpricedis = list[i].dis;}}if (flag == 0 && minprice != Integer.MAX_VALUE) {totalprice += (nowprice * (cmax - leftdis / davg));leftdis = cmax * davg - (minpricedis - nowdis);nowprice = minprice;nowdis = minpricedis;}if (flag == 0 && minprice == Integer.MAX_VALUE) {nowdis += cmax * davg;System.out.printf("The maximum travel distance = %.2f", nowdis);return;}}System.out.printf("%.2f", totalprice);}static class Station implements Comparable<Station> {double price, dis;Station(double p, double d) {price = p;dis = d;}@Overridepublic int compareTo(Station o) {if (dis > o.dis) return 1;else if (dis < o.dis) return -1;else return 0;}}
}
class Read {static BufferedReader br;static StringTokenizer st;static void init(InputStream in) {br = new BufferedReader(new InputStreamReader(in));st = new StringTokenizer("");}public static double nextDouble() throws IOException {return Double.parseDouble(next());}static String next() throws IOException {while (!st.hasMoreTokens()) {st = new StringTokenizer(br.readLine());}return st.nextToken();}static int nextInt() throws IOException {return Integer.parseInt(next());}
}以及gas station那一道题目，和这一道题总是有点关系，给出一系列加油站的储油量和从前一个加油站到后一个加油站的耗油量，问你车辆从哪个站点出发能跑完全程？原题如下
There are N gas stations along a circular route, where the amount of gas at station i is gas[i].
You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.
Return the starting gas station’s index if you can travel around the circuit once, otherwise return -1.
AC代码如下
class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {if (gas == null || cost == null || gas.length == 0 || cost.length == 0 || cost.length != gas.length) return -1;int total = 0, sum = 0, index = -1;for (int i=0; i<gas.length; i++) {int dif = gas[i] - cost[i];sum += dif;total += dif;if (sum < 0) {sum = 0;index = i;}}return total >= 0 ? index + 1 : -1;}
}参考博客一：
参考博客二：