ACMboy

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  4 Posts :: 0 Stories :: 0 Comments :: 0 Trackbacks

常用链接

留言簿

我参与的团队

搜索

  •  

最新评论

阅读排行榜

评论排行榜

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

代码:

#include <iostream>
int main()
{
    
double rest=0,need,p[12],s,c,t,d[12];
    
int n;
    scanf(
"%lf%lf%lf%lf%d",&s,&c,&t,&p[0],&n);
    
for(int i=1;i<=n;i++)
        scanf(
"%lf%lf",&d[i],&p[i]);
    d[
0]=0;
    d[n
+1]=s;
    
int k=0,j=0,min=0,min2=0,back=0;
    
double cost=0;
    
while(k<=n)
  
{
        j
=k;
        
while(d[j+1]-d[k]<=c*t&&j<=n)
      
{
            j
++;
            
if(min==0&&p[j]<p[k]) min=j;
            
if(min2==0||p[j]<p[min2]) min2=j;
        }

        
if(j==k)
      
{
            printf(
"No Solution\n");
            
return 0;
        }

        
if(!min)
      
{
            need
=c-rest;
            cost
+=need*p[k];
            rest
=c-(d[min2]-d[k])/t;
            k
=min2;
        }

        
else
        
{
            need
=(d[min]-d[k])/t-rest;
            
if(need<0)
                need
=0;
            cost
+=need*p[k];
            rest
=0;
            k
=min;
        }

        min
=min2=0;
    }

    printf(
"%.2lf\n",cost);
    
return 0;
}
posted on 2010-04-09 13:48 EG-HUA 阅读(1087) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理