题解 P1016 【旅行家的预算】

衡屿睿 · 2017-09-24 11:16:43 · 题解

简单理一下贪心的思想：

先确定每个节点间的距离，start为0节点，end为n+1节点。

若存在节点间的距离d[i]-d[i-1]大于D*c，则No Solution；其余情况，必有解。

在每个节点，我们有三种选择：

1.如果指定的goal还未完成，继续行驶；

2.若到达了goal，则向前找第一个邮价比自己低的油站（end处油站油价为0）

i.能够开往（distance<=D*c）,则将goal定为它；

ii不够开往（distance>D*c）,将油加满，将goal定为在加满情况下所能开到的最远油站。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;
double d[600]={0},p[600];
double s,c,D,p1;
int n;
double money=0,oil=0;
double locin(int goal,int now)
{
    if(now==n+1)
    {
        printf("%.2lf",money);
        return 0;
    }
    if(now<goal)
    {
        oil-=(d[now+1]-d[now])/D;
        locin(goal,now+1);
        return 0;
    }
    if(now==goal)
    {
        int k=now+1;
        while(p[k]>p[now])k++;
        if(d[k]-d[now]<=D*c)
        {
            if(oil<(d[k]-d[now])/D)
            {
            money+=((d[k]-d[now])/D-oil)*p[now];
            oil=(d[k]-d[now])/D;
            }
            locin(k,now);
            return 0;
        }
        else
        {
            int w=now+1;
            while(d[w]-d[now]<=D*c)w++;
            w--;
            money+=(c-oil)*p[now];
            oil=c;
            locin(w,now);
            return 0;
        }
    }
}
int main()
{
    cin>>s>>c>>D>>p1>>n;
    p[0]=p1;
    for(int i=1;i<=n;++i)
    {
    cin>>d[i]>>p[i];
    if(d[i]-d[i-1]>D*c)    
    {
        cout<<"No Solution";
        return 0;
    }
    }
    d[n+1]=s;p[n+1]=0;
    if(d[n+1]-d[n]>D*c)    
    {
        cout<<"No Solution";
        return 0;
    }
    locin(0,0);
    return 0;
}