贪心算法学习笔记(一)

更好的阅读体验

导言

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

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

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

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

题目描述

一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市(假设出发时油箱是空的)。给定两个城市之间的距离$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:

1
2
3
275.6 11.9 27.4 2.8 2
102.0 2.9
220.0 2.2

输出样例#1:

1
26.95

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

解题报告

题意理解

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

1
No Solution


思路解析

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

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

第三点:为什么要加满油?因为这样可以减少在下一个加油站(价格更贵)所需要加的油量。

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

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

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

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


代码解析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#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;
}