JDOJ-1386: [NOIP1999]旅行家的预算 贪心+语法逻辑

[文章目录]

Description

一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市(假设出发时油箱是空的)。给定两个城市之间的距离d1、汽车油箱的容量c(以升为单位)、每升汽油能行驶的距离d2、出发点每升汽油价格p和沿途油站数n,油站i离出发点的距离d[i]、每升汽油价格p[i]。 计算结果四舍五入至小数点后两位。 如果无法到达目的地,则输出-1。(n<=100)

说实话,如果再出这道题,我很可能被一个零基础的小朋友秒杀掉。。。

没有用到任何的数据结构还有算法。

对于每一个加油站,我们看他后面能走到的加油站,如果有更便宜的加油站,那么只需要加足油使自己能够到达那个加油站即可。如果没有,加满,继续走下一个加油站,看是否需要再加一些油。用一个now存储当前的位置,加ans时判断一下是否已经加够到该地的油(也就是说买完了那些油)。

理论上的确是水题,但是,蒟蒻表示做不到啊。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
double c,v,now,ans;
int n;
struct node
{
    double dis,p;
}a[110];
bool cmp(node x,node y)
{
    return x.dis<y.dis;
}
int main()
{
    scanf("%lf%lf%lf%lf%d",&a[2].dis,&c,&v,&a[1].p,&n);
    a[2].p=0;a[1].dis=0;n+=2;
    for(int i=3;i<=n;i++)
        scanf("%lf%lf",&a[i].dis,&a[i].p);
    sort(a+1,a+n+1,cmp);
    int k=1;
    double mxx=v*c;
    while(k<=n)
    {
        if(a[k+1].dis-a[k].dis>mxx) {cout<<"-1";return 0;}
        int j=k+1;
        while(j<=n&&a[j].dis-a[k].dis<mxx)
        {
            ans+=a[k].p*max(a[j].dis-now,0.0)/v;now=max(now,a[j].dis);
            if(a[j].p<a[k].p){k=j;break;}
            else j++;
        }
        if(k!=j) ans+=a[k].p*(min(a[k].dis+mxx,a[n].dis)-now)/v,now=min(a[n].dis,a[k].dis+mxx),k++;
    }
    printf("%.2lf\n",ans);
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注