PAT 甲级 1033 To Fill or Not to Fill (25 分)（贪心,误以为动态规划,忽视了油量问题）*

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: 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 (≤), the distance between this station and Hangzhou, for ,. 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

题意：

　　从某地开车出发，去目标地点，已知每单位油行驶距离、最大油量、目标城市距离，给你沿途所有加油站的信息，包括油价和距离。求算出能否到达目标城市，如果能，给出最小的开销，如果不能给出最远行驶距离。

题解：

　　乍一眼就觉得是动态规划，看了题解并思考了一会才觉得贪心就够了。这是基于贪心算法的题目，拿最少的钱行驶最远的距离。后来忽略了如果不存在比当前更便宜的站点，那么显然目前这个点是最便宜的，要加满。

　　我们不妨从第一个加油站开始算，比较可到达范围内，最便宜的站点是哪个 :

　　① 如果存在比当前站点还便宜的站点，先到最近的一个站，仅加满到该地的油即可；

　　② 如果不存在比当前更便宜的站点，那么显然目前这个点是最便宜的，先加满再说。然后去范围内相对最便宜的下一个站点；

　　③ 如果下一站不在可达范围内，如果此时已经临近终点，那么输出总开销，如果此时终点也不可达，那么输出最远距离。

AC代码：

#include<bits/stdc++.h>

using namespace std;

struct sta{

    double p,d;

}a[];

bool cmp(sta x,sta y){

    return x.d<y.d;

}

double cm,dist,davg;

int n;

int main(){

    cin>>cm>>dist>>davg>>n;

    for(int i=;i<=n;i++){

        cin>>a[i].p>>a[i].d;

    }

    sort(a+,a++n,cmp);

    int k=;

    double m_range = cm*davg;

    double max_d=;

    double min_p=;

    if(a[].d!=){

        printf("The maximum travel distance = %.2f",max_d);

        return ;

    }

    int can_get,nk;

    double kd,kp,cheapest;

    double oil=;

    while(){

        can_get=;

        kd=a[k].d;

        kp=a[k].p;

        nk=-;

        cheapest=;

        if(kd+m_range>=dist){

            can_get=;

        }

        int cheap=;

        //遍历所能到达的全部站点

        for(int i=k+;i<=n;i++){

             if(a[i].d>kd+m_range || a[i].d>=dist){

                 break;

             }

            //一旦发现有价格更便宜的就停止

            if(a[i].p<kp){

                nk=i;

                cheap=;

                break;

            }

            //否则找一个价格相对便宜的

            if(!can_get&&a[i].p<cheapest){

                cheapest=a[i].p;

                nk=i;

            }

        }

        //cout<<nk<<" "<<a[nk].d<<endl;

        if(nk==-){//已经达到最远了

            if(can_get){

                if(oil<(dist-kd)/davg){

                    min_p += kp*((dist-kd)/davg-oil);

                }

                printf("%.2f",min_p);

            }else{

                max_d=kd+m_range;

                printf("The maximum travel distance = %.2f",max_d);

            }

            break;

        }

        //只要到nk的油量加了就行

        //cout<<"从"<<k<<"到"<<nk<<" 距离:"<<a[nk].d-kd<<" 当前油量:"<<oil<<endl;

        if(!cheap){

            //cout<<"当前为最小点加满,";

            if(oil<cm){

                min_p += kp*(cm-oil);

                oil=cm;

            }

            oil-=(a[nk].d-kd)/davg;

            //cout<<"用了"<<(a[nk].d-kd)/davg<<" 还剩"<<oil<<endl; 

        }else{

            if((oil<a[nk].d-kd)/davg){

                //cout<<"需加"<<(a[nk].d-kd)/davg-oil;

                min_p += kp*((a[nk].d-kd)/davg-oil);

                oil=(a[nk].d-kd)/davg;

            }

            oil-=(a[nk].d-kd)/davg;

            //cout<<"用了"<<(a[nk].d-kd)/davg<<" 还剩"<<oil<<endl;

        }

        k=nk;

        //cout<<endl;

    }

    return ;

}

巴特西