旅行家的预算-题解


看了一下各位大佬的题解,感觉代码有些长,这里介绍一下~~简短的~~简陋的方法(不涉及单调队列,完全按照题面意思的贪心+模拟)

思路

首先将起点和终点与道路上的加油站视为等价节点,按照距离起点的距离(即为通过顺序)排序。
然后对于每一个节点我们可以进行以下贪心策略
- 如果可以直达下一个油价更低的节点就加满够到此节点的油,开过去(中间的不用管)
- 如果不能直达就加满油(因为中转节点的油更贵要少加),开到能到范围内油价最低的加油站\(^{^{[1]}}\)

对于\(^{[1]}\)的证明: 因为从A到B的路程一定,不管是\(A->C->B\)还是\(A->D->B\)所需的油量一定,那么设\(P_b<P_a<P_c<P_d~~D_{ac}<D_{ad}\),在A地加满油需\((C-left)~\cdot~P_a\),C处加油\(cost_c=(D_{cb}/D2-(C-D_{ac}/D2))\cdot P_c\),D处加油\(cost_d=(D_{db}/D2-(C-D_{ad}/D2))\cdot P_c\), 变形为\(cost_c=((D_{cb}+D_{ac})/D2-C)\cdot P_c,cost_d=((D_{cd}+D_{ad})/D2-C)\cdot P_d\) $$\because{D_{ab}=D_{ac}+D_{cb}=D_{ad}+D_{db}}~~\therefore (D_{cd}+D_{ad})/D2-C=(D_{cb}+D_{ac})/D2-C$$ $$\because P_c<P_d~\therefore cost_c<cost_d$$ 然后就是按照策略打代码了


#include <bits/stdc++.h>
double D0,C,D,cost,left;
struct node
{
    double d,p;
}s[8];
int n;
bool cmp(node a,node b){return a.d<b.d;}
int main()
{ 
    scanf("%lf%lf%lf%lf%d",&D0,&C,&D,&s[0].p,&n);
    s[n+1].d=D0;
    for(int i=1;i<=n;i++)
    {
        scanf("%lf%lf",&s[i].d,&s[i].p);
        if(s[i].d-s[i-1].d>C*D)//中间有一段路加满油也到不了下个节点
        {
            printf("No Solution");
            return 0;
        }
    }
    std::sort(s+1,s+1+n,cmp);
    for(int i=0;i<=n+1;)
    {
        int j,k;
        for(j=k=i+1;j<=n;j++)//若直达终点,j++后j为n+1而不是n+2
        {
            k=s[j].p<=s[k].p?j:k;//范围内最小花费
            if(s[j].p<=s[i].p||s[j+1].d-s[i].d>C*D)break;//找到下一个比当前节点便宜的节点或者到不了下个节点
        }
        if(s[j].p>s[i].p)//策略2
        {
            cost+=(C-left)*s[i].p,left=C-(s[k].d-s[i].d)/D;
            i=k;
        }
        else
            cost+=s[i].p*((s[j].d-s[i].d)/D-left),i=j,left=0;//策略1
    }
    printf("%.2lf",cost);
    return 0;
}

        

代码中的C,D,D0和题面不一一对应