华师一附中OI组

标题: P1016 旅行家的预算 [打印本页]
作者: admin    时间: 2018-5-1 15:15
标题: P1016 旅行家的预算
题目描述
一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离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≤6,其余数字≤500
作者: 吴语林    时间: 2018-7-24 22:13
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <cmath>
  4. #include <cstring>
  5. #include <map>
  6. #include <string>
  7. #include <vector>
  8. #include <queue>
  9. #include <stack>
  10. #include <cstdio>
  11. #include <cstdlib>
  12. using namespace std;
  13. double d[1000]={0},p[1000],dm,s,c,money=0,oil=0;
  14. int n;
  15. void aha(int mu,int no,int l)
  16. {
  17.     if(no==n+1)
  18.     {
  19.         printf("%.2lf",money);
  20.         return ;
  21.     }
  22.     if(no<mu)
  23.     {
  24.         int e=l;
  25.         if(p[no]<p[l])
  26.             money-=oil*(p[l]-p[no]),e=no;
  27.         oil-=(d[no+1]-d[no])/dm;
  28.         aha(mu,no+1,e);
  29.         return ;
  30.     }
  31.     else if(no==mu)
  32.     {
  33.         int k=no+1;
  34.         while(p[k]>p[no])
  35.             k++;
  36.         if(d[k]-d[no]<=dm*c)//跑得到
  37.         {
  38.             if(oil<(d[k]-d[no])/dm)
  39.             {
  40.                 money+=((d[k]-d[no])/dm-oil)*p[no];
  41.                 oil=(d[k]-d[no])/dm;
  42.             }
  43.             aha(k,no,no);
  44.             return ;
  45.         }
  46.         else//跑不到
  47.         {
  48.             int t=no+1;
  49.             while(d[t]-d[no]<=dm*c)//跑的越远越好
  50.                 t++;
  51.             money+=(c-oil)*p[no],oil=c;
  52.             aha(t-1,no,no);
  53.             return ;
  54.         }
  55.     }
  56. }
  57. int main()
  58. {
  59.     scanf("%lf%lf%lf%lf%d",&s,&c,&dm,&p[0],&n);
  60.     for(int i=1;i<=n;++i)
  61.     {
  62.         scanf("%lf%lf",&d[i],&p[i]);
  63.         if(d[i]-d[i-1]>dm*c)
  64.         {
  65.             printf("No Solution");
  66.             return 0;
  67.         }
  68.     }
  69.     d[n+1]=s;
  70.     if(d[n+1]-d[n]>dm*c)
  71.     {
  72.         printf("No Solution");
  73.         return 0;
  74.     }
  75.     aha(0,0,0);
  76.     return 0;
  77. }
复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2