旅行家的预算Travel(贪心)

此题是一道经典的贪心题(NOIP1999)

题目描述:

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

input:

275.6 11.9 27.4 2.8 2
102.0 2.9
220.0 2.2

out:

26.95

思路:

先判断无解的情况:在当前加油站加满油都到不了下一个加油站

接下来,遍历加油站,找到比当前加油站更便宜的第一个加油站,如果没有,则油加满,先判断时候能直接跑到终点,跑到范围内,如果跑不到,则跑到最便宜的加油站,执行上一步骤;

```cpp

#include<cstdio>

#include<algorithm>

using namespace std;

double d1,c,d2,Max,oil,cost;

int n,now_i=1;

struct node{

    double di,pi;

}a[100005];

bool cmp(node x,node y){

    return (x.di<y.di);

}

int main(){

    scanf("%lf %lf %lf %lf %d",&d1,&c,&d2,&a[1].pi,&n);

    for(int i=2;i<=n+1;i++){

        scanf("%lf %lf",&a[i].di,&a[i].pi);

    }

    a[n+2].di=d1;

    Max=c*d2;

    sort(a+2,a+2+n,cmp);

    for(int i=2;i<=n+2;i++){

        if(a[i].di-a[i-1].di>Max){

            printf("No Solution");

            return 0;

        }

    }

    while(1){

        bool flag=0;

        int next,k;

        double minn=10000;

        for(int i=1+now_i;a[i].di-a[now_i].di<=Max&&i<=n+1;i++){

            if(a[i].pi<=a[now_i].pi&&!flag){

                next=i;

                cost+=((a[i].di-a[now_i].di)/d2-oil)*a[now_i].pi;

                flag=1;

                oil=0;

                break;

            }

            if(!flag&&a[i].pi<minn){

                minn=a[i].pi;

                k=i;

            }

        }

        if(!flag){

            if(d1-a[now_i].di<=Max){

                cost+=((d1-a[now_i].di)/d2-oil)*a[now_i].pi;

                break;

            }

            else{

                next=k;

                cost+=a[now_i].pi*(c-oil);

                oil=c-(a[k].di-a[now_i].di)/d2;

            }

        }

        now_i=next;

    }

    printf("%.2lf",cost);

    return 0;

}

 ```

上一篇:暑假ACM训练计划


下一篇:第六周ACM训练报告