[普及+/提高]P1016 旅行家的预算

题目链接：https://www.luogu.com.cn/problem/P1015

思路分析

车辆从起点到达目标地点所需要的总油量是一定的，若要使最终的总油费最便宜，也就是尽可能地在油价便宜的加油站加油，这一点是必须要明确的，当然大家也能够想到这一点，典型的贪心。

车辆在行驶的过程中，在某一个加油站补充了汽油后，即使行驶到下一站发现这一站的汽油价格更便宜，车中的油也不能用这一站便宜的汽油来替代。以起点出发为例，即使距离起点的第一个加油站的汽油价格明显比起点的加油站的汽油价格便宜，一开始也还是需要加起点的加油站的贵一点的汽油，这一部分油是必须要加的，不管有多贵，不然车辆就不能启动了！在这种不知道下一个加油站的汽油价格的情况下，你只能希望车辆能够到达目的地就行（假设不是impossible的情况）

可当你经过了多个加油站后，比如当你到达了某个加油站，若你发现你现在所在的加油站的汽油价格比上一个加油站的汽油价格贵时，你可能会想：“要是我在前一个加油站多加点油就好了！”竟然如此，我们就给他时光逆流的机会！

假设三个加油站，分别为 1、2、3号加油站，正常行驶方向是 1→2→3，1→2的油是在1号加油站加的，2→3的油是2号加油站加的。我们现在将这个过程逆过来，将车辆从2→1行驶，当你发现1号加油站的汽油价格比2号便宜的时候，你会怎么做？是不是将在2号加油站加的部分汽油换成1号加油站的汽油？（注意是2号加油站的部分汽油，因为油箱容量有限，有可能无法全部替换，也有可能全部替换，到后面看图就知道了）然后计算价格的时候，只要减去油价差就可以了。

直观一点，还是看图吧，文字太多重复，看着不免会眼花。。。

最后附上我的代码吧，注释懒得写了，程序没写准确没关系，关键是要自己想明白这个问题哦！

代码

#include<cstdio>
#include<iostream>
using namespace std;
double d[507];
double p[507];
int main(){
    int N;
    double D1,C,D2,P,maxdistance,minprice,fare=0,exmeter;
    cin>>D1>>C>>D2>>P>>N;
    maxdistance=C*D2;
    d[0]=0;d[N+1]=D1;p[0]=P;p[N+1]=0;
    for(int i=1;i<=N;i++) cin>>d[i]>>p[i];
    for(int i=N;i>=0;i--){
        fare+=p[i]*(d[i+1]-d[i])/D2;
        int n=i;exmeter=maxdistance-(d[i+1]-d[i]);
        if(exmeter<0){
            cout<<"No Solution";
            return 0;
        }
        minprice=p[n+1];
        while(n<N){
            if(p[i]<minprice&&exmeter>0){
                if(exmeter>d[++n+1]-d[n]){
                    exmeter-=d[n+1]-d[n];
                    fare-=(minprice-p[i])*(d[n+1]-d[n])/D2;
                }
                else fare-=(minprice-p[i])*exmeter/D2;
                if(p[n+1]<p[n]) minprice=p[n+1];
            }
            else break;
        }
    }
    printf("%0.2f",fare);
}

时间复杂度不会超过N*N，并且比N*N差了很多，应该不会超时的啦，通过样例所用时间大概是3ms/个。

此题思路有很多种，这只是我的思路，不是标准答案，也不算是什么最优解法。这个题目我用的算法大概就是 递归 了吧，很多大佬用的是贪心+模拟或者单调队列什么什么的，可能是菜鸡的我掌握的算法或者数据结构太少了QAQ