更好的阅读体验

导言

贪心算法的核心:就是局部最优到达全局最优,每一步都保证最优.

切记这里的最优,是符合题目条件的最优,往往都是题目的目标.

贪心算法没有固定的框架,但是有几大模型,从现在起我们来一步步解析.

本文为贪心学习笔记一,还有后续,欢迎各位继续阅读.

题目描述

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

输入输出格式

输入格式：
第一行，$D1$，$C$，$D2$，$P$，$N$。

接下来有$N$行。

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

输出格式：

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

输入输出样例
输入样例#1：

275.6 11.9 27.4 2.8 2
102.0 2.9
220.0 2.2

输出样例#1：

26.95

说明
$N \le 6$,其余数字$ \le 500$

解题报告

题意理解

就是在一个长度为$D1$的数轴上,有N个加油站,起点(原点)上也有一个加油站,每一个加油站,有专属于它的加油价格.
现在你要从原点到终点,要求花费的价格最低.切记你的油箱最多只能装$C$升.
如果到达不了,则输出

No Solution

思路解析

我们很容易想到一个贪心思路.

我们当然是要在油价低的油站多加油,在油价高的油站少加油

第三点：为什么要加满油？因为这样可以减少在下一个加油站（价格更贵）所需要加的油量。

1. 对于两个相邻的油站$D_i$和$D_{i+1}$而言,如果说$i+1$油站的代价更少,那么显然我们在$i$油站加的油,就是两者距离所花费的油.

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

3. 如果在这个加油站即使加满油，都不能到达任意一个加油站，也不能到达终点城市，说明无解,程序结束.

综上所述,这道题目就解决了.

代码解析

#include <bits/stdc++.h>
using namespace std;
const int N=110;
int i,j,n;
double d1,d2,c,w,ans,p[N],d[N],s[N];
int main()
{
    cin>>d1>>c>>d2>>p[0]>>n;//按照题目意思读取
    for(int i=1; i<=n; i++)
        cin>>d[i]>>p[i];
    d[n+1]=d1;//可以认为最后一个加油站就是终点.
    d[0]=0;//起点加油站距离为0
    for(int i=0; i<=n; i++)
        s[i]=(d[i+1]-d[i])/d2;/处理两个相邻油站,从i到i+1,他们所需要花费的油
    while(i<n)
    {
        j=i+1,w=c;
        while(p[i]<p[j] && w)//如果发现i加油站,比j加油站价格低,而且油没有装满
        {
            double now=min(s[j],w);//避免油箱装满
            if (s[i]+now>c)//避免出界
                now=c-s[i];
            s[i]+=now;//多装now个油
            s[j]-=now;//少装now个油
            w-=now;//剩余油量减少
            j++;//下一个加油站
        }
        i=j;
    }
    for(int i=0; i<=n; i++)
    {
        if (s[i]>c)
        {
            puts("No Solution");//无解快乐
            return 0;
        }
        ans=ans+p[i]*s[i];//统计每一个加油站要加的油
    }
    printf("%.2lf",ans);
    return 0;
}