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

一道贪心+模拟题

思路:

分为三种情况:范围内的加油站比自己便宜,范围内的加油站都比自己贵,范围内的加油站都比自己贵但是能直接到达终点

设计算法知识并不难,难的是各种恶心的数学公式,一个个拿出来也并不难。连在一起就看着很复杂

两点之间的距离 d[i]-d[i-1]
到某一个价格便宜的加油站点所耗费的钱((d[ii]-d0)/d2-l)*p
直接加满油费用 pz+=(c-l)*p
距离到达终点花费费用((d1-d0)/d2-l)*p
油箱里还剩多少油l-(d[ii]-d0)/d2

题解自:洛谷101559号


#include<cstdio>
#include<iostream>
using namespace std;
double d[10],pi[10];
int main()//愉快地开始了主函数 
{
    double d1,c,d2,p,pmin=1000,l=0,pz=0;//l指的是油箱中的油量,初始值为0;pz指的是所花的钱的总数,初始值为0 
    //d1 两个城市之间距离 c汽车油箱容量 
	//d2每升汽油能行驶的距离 p出发点每升汽油的价格
    int n;
    cin>>d1>>c>>d2>>p>>n;
    d[0]=0;
    double d0=0;
    pi[0]=p;
    double x=c*d2;//x指的是加满油能最多能走的里程 
    for(int i=1;i<=n;i++)
    {
        cin>>d[i]>>pi[i];
    }
    for(int i=1;i<=n;i++)
    {
        if(d[i]-d[i-1]>x){cout<<"No Solution";return 0;}//无解的情况其实就是相邻加油站之间的距离超过了x,把无解的情况全部揪出来 
    }
    int ii=0;
    while(d1-d0)//d1是总路程,d0就是移动的距离,如果d1-d0=0,那么就意味着旅行家到达终点; 
    {
        for(int i=ii+1;d[i]-d0<=x&&i<=n;i++)
        {
            if(pi[i]<pmin){pmin=pi[i];ii=i;}
        }
        if(pmin<=p){pz+=((d[ii]-d0)/d2-l)*p;l=(d[ii]-d0)/d2;} //范围内的加油站比自己还便宜,那就使加的油刚好能支持到达这个加油站 
        else if(d1-d0>x) //这种情况指的是范围内的加油站都比自己贵,并且无法一次到达终点,所以应该在自己这个最便宜的加油站直接加满 
        {
            pz+=(c-l)*p;
            l=c;
        }
        else//这种情况 指的是范围内的加油站都比自己贵,但能一次到达终点,那我肯定不管后面加油站了,直接奔向终点 
        {
            pz+=((d1-d0)/d2-l)*p;break; //到达终点就可以break了 
        }
        l=l-(d[ii]-d0)/d2;//走多少里程,就相应地减去多少油 
        d0=d[ii];//更新d0,表示旅行家的移动 
        p=pmin;//更新p,方便下次进行比较 
        pmin=1000;//还原pmin,以便下次搜索最小值 
    }
    printf("%.2lf",pz);//保留两位小数输出 
    return 0; //愉快地结束了主函数 
}