Traveler's budget

Title Description

A traveler wants to drive a car from one city to another at the least cost (assuming the fuel tank is empty at the time of departure). Given the distance D1 between the two cities, the capacity C of the automobile fuel tank (in liters), the distance D2 that can be driven per liter of gasoline, the price P of gasoline per liter of the starting point and the number of stations along the way (n can be zero), the distance Di that the station i is from the starting point, the price Pi per liter of gasoline (i=1, 2 ,N). The calculation results are rounded to two decimal places. If the destination cannot be reached, output "No Solution".

I / O format

Input format:
The first line, D1, C, D2, P, N.

Next there are N lines.

Line i+1, two numbers, distance from the starting point of station i Di and price per litre of gasoline Pi.

Output format:
The minimum cost required shall be rounded to two decimal places. If the destination cannot be reached, output "No Solution".

N ≤ 6, others ≤ 500

Ideas:

The greed of a ghost animal...

At first, I was naive. I think it's very simple! Look forward to the smallest gas station until it ends. Results Listen to WA
Then, I was so naive that I thought I would quit when I found a smaller gas station than the current one, and I got stuck at one point. I was naive and thought it was a precision problem

So, I realized! If there's no gas station

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
double ass=0,l,t,v,b[555],a[555],ess=0;
int n;
int main()
{

    scanf("%lf%lf%lf%lf%d",&l,&t,&v,&b[0],&n);
    for(int i=1; i<=n; i++) scanf("%lf%lf",&a[i],&b[i]);
    double s=0;
    int total=0;
    a[n+1]=l; b[n+1]=0;
    while (s<l)
    {

        int minn=0; double minv=2147483647;
        for(int i=total+1; i<=n+1; i++)
        {

            if (s+t*v<a[i])
            {
                i--; break;
            }

            if (b[i]<b[total])
            {
                minn=i; minv=b[i]; break;
            }
            if (b[i]<minv)
            {
                minn=i; minv=b[i];
            }

        }
        if(minn==total) 
        {
            printf("No Solution");
            return 0;
        }
        ess=0;
        if (b[total]<b[minn]) 
        {
            ass+=t*b[total]; 
            ess=s+v*t-a[minn];
        }else
        ass+=(a[minn]-s)*b[total]/v;
        s=a[minn]+ess; total=minn;
        if (total>=n+1) break;

    }
    printf("%.2lf",ass);

}

Posted on Fri, 01 May 2020 10:31:06 -0700 by obesechicken13