首页 > 代码库 > NOIP1999 旅行家的预算

NOIP1999 旅行家的预算

题目描述

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

 题解:

贪心策略就是选择去最近的比当前站便宜的加油站,若没有,就在该站把油加满走最远的加油站。

#include<stdio.h>int n;double d1,d2,c,d[101],p[101],ans,rst;int main(){    scanf("%lf%lf%lf%lf%d",&d1,&c,&d2,&p[0],&n);    d[n+1]=d1;    for(int i=1;i<=n;i++)        scanf("%lf%lf",&d[i],&p[i]);    for(int i=0;i<=n;i++)        if(d[i+1]-d[i]>c*d2){            puts("No Solution");            return 0;        }    for(int tag=-1,i=0;i<=n;i=tag,tag=-1){        for(int j=i+1;(!(tag^(-1)))&&j<=n+1;j++)            if(c*d2>d[j]-d[i]&&p[i]>p[j])                tag=j;        if(tag^(-1)){            if(rst>(d[tag]-d[i])/d2)                rst-=(d[tag]-d[i])/d2;            else                ans+=((d[tag]-d[i])/d2-rst)*p[i],                rst=0;        }        else{            for(int j=n+1;j>i;j--)                if(c*d2>=d[j]-d[i]){                    tag=j;                    break;                }            ans+=(c-rst)*p[i];            rst=c-(d[tag]-d[i])/d2;        }    }    printf("%.2lf\n",ans);}

 

NOIP1999 旅行家的预算