旅行家的预算(NOIP1999&水题测试2017082301)

题目链接：旅行家的预算

这题还可以，不算太水。

这题贪心即可。

我们采取如下动作：

如果在装满油的情况下能到达的范围内，没有加油站，则无解。
如果在装满油的情况下能到达的范围内，油价最低的加油站的油价比当前高，那就装满油再走。
如果在装满油的情况下能到达的范围内，油价最低的加油站的油价比当前低，我们使油够到达那个加油站即可，如果当前的油比需要的多，我们分两种情况考虑：第一，这个最低油价比上一个加油的站价格高，那么我们就直接过去；第二，这个最低油价比上一站油价低，那么我们把多余的油退回上一个加油站（没错，就是有这种操作）。
如果能到达终点，我们依然要考虑两种情况：第一，就是最低油价比当前站油价低，那就执行3；第二，如果最低油价比当前站油价高，那就直接过去，并判断油是否多余，多余就退。

有了这几点，我们就可以写出程序了。

#include<bits/stdc++.h>

using namespace std;

int main(){

    int reachable=1;

    double d1,c,d2,P;

    int n;

    scanf("%lf%lf%lf%lf%d",&d1,&c,&d2,&P,&n);

    double d[n+2],p[n+2];

    double ans=0.0;

    double liter=0.0;                    //1

    int laststop=0;                       //2

    d[n+1]=d1,p[n+1]=0;                   //3

    d[0]=0,p[0]=P;

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

        scanf("%lf%lf",&d[i],&p[i]);

    }

    double maxgo=c*d2;                    //4

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

        double min=1000000000.0;

        int x=-1;

        int ok=0;

        for(int j=i+1;j<=n+1&&d[j]-d[i]<=maxgo;j++){//5

            if(j==n+1){

                ok=1;

            }else if(p[j]<min){

                min=p[j];

                x=j;

            }

        }

        if(ok==1&&min>=p[i]){

            double need=(d[n+1]-d[i])/d2;

            if(liter<need){

                ans+=(need-liter)*p[i];

            }else{

                ans-=(need-liter)*p[laststop];

            }

            liter=0;

            laststop=i;

            i=n+1;

        }else if(x>=0){

            if(min>p[i]){

                double need=c-liter;

                ans+=need*p[i];

                liter=c-(d[x]-d[i])/d2;

            }else{

                double need=(d[x]-d[i])/d2;

                if(need>liter){

                    ans+=(need-liter)*p[i];

                    liter=0;

                }else{

                    if(p[x]<p[laststop]){

                        ans-=(need-liter)*p[laststop];

                        liter=0;

                    }else{

                        liter-=need;

                    }

                }

            }

            laststop=i;

            i=x;

        }else{

            reachable=0;

            break;

        }

    }

    if(reachable){

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

    }else{

        printf("No Solution");

    }

    return 0;

}

就提五处：

1处：保存当前油量

2处：保存上一站

3处：我们这里视起点为第0站，终点为第n+1站。

4处：计算满油能跑的路程

5处：求最小值

巴特西

旅行家的预算(NOIP1999&水题测试2017082301)

最新文章

热门文章