1033 To Fill or Not to Fill （25 分)

2019-03-16

1033 To Fill or Not to Fill （25 分)

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: Cma**x (≤ 100), the maximum capacity of the tank; D (≤30000), the distance between Hangzhou and the destination city; Dav**g (≤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: P**i, the unit gas price, and D**i (≤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:

1
2
3

50 1300 12 2
7.10 0
7.00 600

Sample Output 2:

1	The maximum travel distance = 1200.00

作者: ZHANG, Guochuan

单位: 浙江大学

时间限制: 200 ms

内存限制: 64 MB

代码长度限制: 16 KB

题目大意

从杭州要去一个地方，给出沿途cmax邮箱容量，D距离，Davg油耗，N沿途加油站数。接下来N行为N个加油站，给出油价及距离。问从杭州到目的地，最低的油价是多少。如果不能到达，输出能开到的最远距离。

分析

一开始考虑的是动态规划，想了一会没想出来，还是参考了柳婼のblog，使用贪心算法即可，在写一些自己的理解吧。

出发时车是没油的，如果0的位置没有加油站，那么是开不动的，直接输出。
利用now记录车辆当前所在位置。每次考虑从now出发汽车能开到最远距离内的加油站。此处分为两种情况：
1. 此范围内有比当前位置油价更便宜的加油站。那么就在当前加油站加油，加至距离正好到该加油站即可。注意这个加油站只需要是沿途第一个更便宜的就行，不需要是整个范围内最便宜的。因为开过去就能加更便宜的油。
2. 此范围内没有更便宜的加油站。那么在当前加油站加满，并且将车开至范围内最便宜的加油站。
在终点处添加一个加油站，油价设为0。这样终点处的权重就会是最高的。

总而言之，就是考虑汽车能开到的最远距离内，哪里便宜就在哪里加油。

代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
#include <map>
#include <set>
#include <cstring>
#include <cmath>
#include<sstream>

using namespace std;
struct station {
    double price;
    int dis;
};

bool cmp(station s1, station s2) {
    return s1.dis < s2.dis;
}

int main() {
    int cmax, d, davg, n, inf = 9999999;
    //now-汽车当前位置，left-剩余油可开里程，maxtogo-能开最远距离
    double now, left, maxtogo;
    cin >> cmax >> d >> davg >> n;
    double cost = 0, curprice;
    vector<station> stas(n + 1);
    stas[0].price = 0;
    stas[0].dis = d;
    for (int i = 1; i <= n; i++) {
        cin >> stas[i].price >> stas[i].dis;
    }
    sort(stas.begin(), stas.end(), cmp);

    if (stas[0].dis != 0) {
        cout << "The maximum travel distance = 0.00";
        return 0;
    } else {
        now = 0;
        left = 0;
        curprice = stas[0].price;
    }
    while (now < d) {
        maxtogo = now + davg * cmax;
        double minprice = inf;
        int flag = 0;
        double nextsta = 0;
        for (int i = 1; i <= n && maxtogo >= stas[i].dis; i++) {
            if (stas[i].dis <= now)continue;
            //存在比当前更便宜的加油站，直接开过去
            if (curprice > stas[i].price) {
                cost += (stas[i].dis - now - left) / davg * curprice;
                left = 0;
                now = stas[i].dis;
                curprice = stas[i].price;
                flag = 1;
                break;
            }
            //记录沿途较便宜加油站
            if (stas[i].price < minprice) {
                minprice = stas[i].price;
                //记录最便宜加油站位置
                nextsta = stas[i].dis;
            }

        }
        //开至较便宜加油站
        if (flag == 0 && minprice != inf) {
            cost += curprice * (cmax - left / davg);
            left = cmax * davg - (nextsta - now);
            curprice = minprice;
            now = nextsta;
        }
        //无法开到任何一个加油站
        if (flag == 0 && minprice == inf) {
            now += cmax * davg;
            printf("The maximum travel distance = %.2f", now);
            return 0;
        }
    }
    printf("%.2f", cost);
    return 0;
}

其他

此代码在PAT上AC，但是在牛客网上测试数据非常奇葩，同一个位置有好几个不同价格的加油站，需要略加改造。