【洛谷】【贪心】P1016 [NOIP1999 提高组] 旅行家的预算

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

题目描述

一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离D1、汽车油箱的容量C*（以升为单位）、每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途油站数NN*（N可以为零），油站i离出发点的距离Di、每升汽油价格Pi（i=1,2,…,Ni=1,2,…,N）。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“No Solution”。

输入格式

第一行，D1，C，D2，P，N。

接下来有N行。

第i+1行，两个数字，油站i离出发点的距离Di和每升汽油价格Pi。

输出格式

所需最小费用，计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“No Solution”。

测试样例

输入
275.6 11.9 27.4 2.8 2
102.0 2.9
220.0 2.2

输出
26.95

解题思路

1.枚举途中经过的加油站，每经过一个加油站，计算一次花费；

2.在一个加油站所需要加的油，就是能够支持它到达下一个油价比它低的加油站的量；

3.如果在这个加油站即使加满油，都不能到达一个比它油价低的加油站，就把油箱加满，前往能够到达的加油站中油价最低的那个；

4.如果在这个加油站即使加满油，都不能到达任意一个加油站，也不能到达终点城市，说明无解；

AC代码

#include
using namespace std;

double d[10],pp[10];

int main()
{
    double d1,c,d2,p;
    int n;
    cin>>d1>>c>>d2>>p>>n;
    d[0] = 0;
    pp[0] = p;
    double dis_max = d2 * c;
    double pri_min = 505;
    double d0 = 0, l = 0, sum = 0;
    for(int i=1;i>d[i]>>pp[i];
    }
    //无解的情况其实就是相邻加油站之间的距离超过了x，把无解的情况全部揪出来
    for(int i=1;idis_max)
        {
            cout