codevs 1046 旅行家的预算

传送门

1046 旅行家的预算

1999年NOIP全国联赛普及组NOIP全国联赛提高组

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 黄金 Gold题解

题目描述 Description

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

输入描述 Input Description

第一行D1 C D2 P N

之后N行，每行2个数表示离出发点的距离Di和每升汽油的价格Pi

输出描述 Output Description

最消费用，保留2位小数

样例输入 Sample Input

275.6 11.9 27.4 2.8 2

102.0 2.9

220.0 2.2

样例输出 Sample Output

26.95

数据范围及提示 Data Size & Hint

N<=100

【题目大意】

开车从一个点到另一个点，行驶道路需要耗油，路上有N个加油站，问能否到达和最小花费。

【思路】

贪心

能行驶到比当前油费更少的加油站就开过去，不能则加满油。

如果在当前加满油仍行驶不到下一个加油站则no solution

【code】逼我搜题解

#include<iostream>

#include<cstdio>

using namespace std;

double D1,C,D2,P;

int N;

int now,mgood=;

double d[],p[],over[];

double ans,s;

int main() {

//    scanf("%lf%lf%lf%lf%lf",&D1,&C,&D2,&P,&N);

cin>>D1>>C>>D2>>P>>N;

    for(int i=; i<=N; i++) {

    //    scanf("%lf%lf",&d[i],&p[i]);

    cin>>d[i]>>p[i];

        if(d[i]-d[i-]>C*D2) {

            printf("No Solution\n");

            return ;

        }

    }

    d[]=;

    d[N+]=D1;

    p[]=P;

    p[N+]=;

    while(now!=N+) {

        s=;

        while(s<=C*D2&&now<=N+&&mgood<=N+&&p[mgood]>=p[now]) {

            mgood++;

            s=s+d[mgood]-d[mgood-];

        }

        if(s<C*D2) {

            if(over[now]>d[mgood]-d[now]) {

                over[mgood]=over[now]-d[mgood]+d[now];

            } else {

                ans+=(d[mgood]-d[now]-over[now])/D2*p[now];

                over[mgood]=;

            }

        } else {

            ans+=(C*D2-over[now])/D2*p[now];

            mgood=now+;

            over[mgood]=(C*D2)-(d[mgood]-d[now]);

        }

        now=mgood;

    }

//    cout<<ans;

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

    return ;

}

【code2】求助最后一个点orz

#include<iostream>

#include<cstdio>

using namespace std;

double d[],p[],over[];

int now,k,s;

double ans,D1,C,D2,P,N;

int main() {

    cin>>D1>>C>>D2>>P>>N;

    for(int i=; i<=N; i++) {

        cin>>d[i]>>p[i];

        if(d[i]-d[i-]>D2*C) {

            printf("No Solution\n");

            return ;

        }

    }

    d[]=,p[]=P;

    while() {

        s=;

        for(k=now+; k<=N; k++) {

            if(p[k]<p[now]) {

                s=k;

                break;

            }

        }

        if(!s) {

            ans+=(D1-d[now])/D2*p[now];

            break;

        } else {

            ans+=(d[s]-d[now])/D2*p[now];

            now=s;

        }

    }

    printf("%.2lf\n",ans);

    return ;

}

巴特西

codevs 1046 旅行家的预算

传送门

1046 旅行家的预算

最新文章

热门文章