[贪心][模拟]SSL P1081 旅行家的预算

Description

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

Input

D1=275.6 C=11.9 D2=27.4 P=2.8 N=2
油站号I 离出发点的距离Di 每升汽油价格Pi
1　　　　102.0　　　　　　　2.9
2　　　　220.0　　　　　　　2.2

Output

26.95（该数据表示最小费用）

Sample Input

275.6　11.9　27.4　2.8　2
102.0　2.9
220.0　2.2

Sample Output

26.95

题解

这题可以用贪心解
如果当前点加满油都跑不到下一个点，直接输出No Solution
如果当前点的油价比下一个点贵，而且这个点不加油又可以跑到下一个点，那不储油
如果当前站点油的价格比下一个站点油的价格低，那么就一直跑，跑到碰到一个站点油的价格比它低，或者是跑到能跑到的最远的站
耗油分两种情况：
①油箱里剩余的油的单价比当前点的油的单价高，不用剩余的油，用当前点的油，耗费只加上实际需要的油的价格
②油箱里剩余的油的单价比当前点的油的单价低，先用完剩余的油，再用当前点的油，耗费加上剩余的油的价格再加上当前站点实际需要的油的价格

代码

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstdlib>
 4 using namespace std;
 5 double d1,c,d2,d[10001],p[10001];
 6 int n;
 7 void dfs(int now,double price,double leave,double x)
 8 {
 9     if(now==n)
10     {
11         printf("%.2lf",price);
12         exit(0);
13     }
14     if(d[now]+c*d2<d[now+1])
15     {
16         printf("No Solution");
17         exit(0);
18     }
19     if(p[now+1]<p[now]) dfs(now+1,leave*x+((d[now+1]-d[now])/d2-leave)*p[now],0,0);
20     else
21     {
22         int z=c*d2,i; 
23         for(i=now+1;i<=n;i++) if(d[now]+z<d[i]) break;
24         i--;
25         int j;
26         for(j=now+1;j<=i;j++) if(p[j]<p[now]) break;
27         if(j==i+1) j=i;
28         if(j==n+1) j=n;
29         if(p[now]<x) 
30         dfs(j,price+(d[j]-d[now])/d2*p[now],c-(d[j]-d[now])/d2,p[now]);
31         else
32         {
33             double tot=(d[j]-d[now])/d2; 
34             tot-=leave;
35             dfs(j,price+tot*p[now]+leave*x,c-tot-leave,p[now]);
36         }
37     }
38 }
39 int main()
40 {
41     cin>>d1>>c>>d2>>p[0]>>n;
42     for(int i=1;i<=n;i++) cin>>d[i]>>p[i];
43     d[++n]=d1;
44     p[n]=1000000;
45     dfs(0,0,0,0);
46 }