问题 C: [普及组模拟赛0811]旅行预算

Question

题目描述

在国庆期间，聪聪想从南京出发到常州找他的弟弟笨笨玩。他刚刚考了驾照，妈妈又允许他使用家里的轿车，于是就决定自己开车去。
聪聪从南京的一个加油站出发（这时油箱是空的）。沿途会有很多加油站，聪聪可以在某些加油站进去加油，且不一定每次都要把油箱加满。需要注意的是，每个加油站的费用不一定相同。我们都知道现在的油价非常贵，所以聪聪希望他在路上为汽油花费的钱尽可能少。现在请你帮助他计算最小的花费。

输入格式
输入文件trip.in包含N+2行。
第1行只包含一个正整数N，表示沿途的加油站的数量（包含出发点）。
第2行包含3个实数D、C、d0，分别表示南京与常州的距离、汽车油箱的最大容量（单位是升）、每升汽油所能行驶的距离。
第3到N+2行，每行包含两个实数，其中第i+2行的两个数di、pi分别表示第i个加油站与南京的距离、该加油站每升油的费用。输入数据保证di随着i的增大是单调递增的，且d1=0。

输出格式
如果聪聪无法到达目的地，则输出“Poor Congcong”，否则输出一个实数，表示最小花费，结果保留2位小数。

输入样例 复制
3
275.6 11.9 27.4
0.0 2.8
102.0 2.9
220.0 2.2
输出样例 复制
26.95
数据范围与提示

对于40%的数据，n≤10。
对于60%的数据，n≤8000。
对于全部的数据，n≤500000。
前70%的数据都是完全随机生成的。
保证输入数据、所有计算过程的中间结果、输出不超过双精度实型（Double）的范围。

Answer 1

【题解】旅行家的预算（贪心）_cqbzlydd的博客-CSDN博客 八中OJ洛谷这题太复杂了，能否全A看数据。。。很好的一道模拟贪心题算法原理（优先级）如下：1.枚举途中经过的加油站，每经过一个加油站，计算一次花费2.在一个加油站所需要加的油，就是能够支持它到达下一个油价比它低的加油站的量；3.如果在这个加油站即使加满油，都不能到达一个比它油价低的加油站，（1）就把油箱加满，前往能够到达的加油站中油价最低的那个；（2）或者直接到终点；4.如果在这个... https://blog.csdn.net/cqbzlydd/article/details/104137764

#include<cstdio> 
#include<algorithm>
#include<cstring>
using namespace std;
double d1,c,d2,n,p1,lc,ans,yx;
struct liu{
    double d,p;
}a[10005];
int main() {
    scanf("%lf%lf%lf%lf%lf",&d1,&c,&d2,&p1,&n);
    lc=c*d2;
    for(int i=1;i<=n;i++) scanf("%lf%lf",&a[i].d,&a[i].p);
    double i=0,yq=p1;
    while(i<d1) {
        double t=i+lc,_min=1e9;
        int bh=0;
        for(int j=1;j<=n;j++) {//在范围内寻找能省钱且最近的 
            if(a[j].d>i&&a[j].d<=t&&a[j].d<d1&&a[j].p<yq&&a[j].d<_min) {
                bh=j,_min=a[j].d;
            } 
        } 
        if(bh!=0) ans+=((a[bh].d-i)*yq-yx)/d2,i=a[bh].d,yq=a[bh].p,yx=0;
        //剩余油不可能直接使到达 
        
        //不能找到，分为能否直接到达终点以及有无后续加油站两方面同时考虑 
        else {
            _min=1e9,bh=0;
            for(int j=1;j<=n;j++) {//在范围内寻找最便宜（并不省钱）的加油站 
                if(a[j].d>i&&a[j].d<=t&&a[j].d<d1&&a[j].p<_min) _min=a[j].p,bh=j;
            }
            //无后续加油站且无法直接到达终点 
            if(bh==0&&t<d1) {
                printf("No Solution");
                return 0;
            }
            //能直接到达，最划算 
            if(t>=d1) {
                if(yx<(d1-i)/d2) {
                    ans+=((d1-i)/d2-yx)*yq;
                }
                break;
            }
            
            //不能直接到达但有后续加油站，先加满（省钱），记录剩余油的多少
            //加满和到最便宜的地方是关键 
            else {
                ans+=(c-yx)*yq;
                yx=c-(a[bh].d-i)/d2;
                yq=a[bh].p,i=a[bh].d;
            }
        }
    }
    printf("%.2lf",ans);
}