# P1016 [NOIP1999 improvement group] traveler's budget

This question, wow, took me a long time. I'm too delicious, so I decided to write a blog and sort out my ideas~

Let's look at the topic first

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 gasoline price P per liter at the starting point and the number of service stations N along the way (N can be zero), the distance Di between the service station i and the starting point and the gasoline price Pi per liter (i=1,2,..., Ni=1,2,..., N). The calculation result is rounded to two decimal places. If the destination cannot be reached, output "No Solution".

Ideas are presented

I won't talk about my waste ideas. Waste time and record the feasible ideas

First, sort

Sort by the distance from the starting point from near to far

A for loop traverses the ordered array. When the next site is found:

(1) After refueling at the current station, you can reach the next station (that is, the distance between the two stations is less than the current maxn, maxn: the longest distance that the oil in the current tank can go), and the oil at this station is cheaper than that at the current station.

Because we can find such a site, how much oil do we only need to add to the current site? When you arrive at that station, the fuel consumption code corresponds to res=0

Why can the first qualified site found by the for loop be used? Isn't there anything cheaper after the for loop

A: because the sites are arranged according to the distance, although the currently found sites are not necessarily cheaper than those in the back, the greedy strategy only depends on the moment. It is more appropriate to change into cheaper oil at the moment than to go to the back with expensive oil before.

So the code is like this:

if(st[i].price<st[now].price)//Can you get & & cheap { price_sum+=(st[i].dis-st[now].dis)/d2*st[now].price; res=0;//res stands for the amount of remaining oil and the distance that can be traveled return i; }

(2) Find the site that can be reached, but it is not cheaper than the current site. At this time, our strategy is to go the farthest with the cheapest oil

So at this time, we need to use a tag variable to mark the last executable of the for loop. Why? Because you want to go to the farthest place with the cheapest oil, the current site is the cheapest, and the for route is more expensive than him

Why is the for loop more expensive than him at this time?

Because if there is one cheaper than him, it will return in the above code.

So the code is like this:

if(index==wrong||st[i].price<st[index].price) index=i;//but it's not cheap

(1) And (2) are in a for loop, and the next situation is out of the for loop, that is, the subsequent extension of (2)

The first: Although there is no cheaper site, you can go directly to the end after refueling the current site

if(d1-st[now].dis<=maxn)//There is no cheaper one, and we can reach the end { price_sum+=(d1-st[now].dis-res)/d2*st[now].price; return wrong; }

The second is that the for cycle just now didn't find a station to go (that is, even if the station is full, it can't go to the next station or destination)

if(index==wrong) { //I can't get to the next stop cout<<"No Solution"<<endl; return -1; }

The third kind: in general, we use the cheapest oil to the farthest station he can walk to, and then refuel

else//There's no cheaper one, and you can't get to the end all at once { price_sum+=c*st[now].price; res+=(maxn-(st[index].dis-st[now].dis)); return index; }

Well, that's the idea. Sort it out and look at the code~

Complete code

#include <bits/stdc++.h> using namespace std; typedef struct { double dis; double price; }station; int wrong=99999; station st[100000]; double d1,c,d2,p; int n; int now;//Current location int t; double maxn;//Where is the farthest double res;//surplus; double price_sum=0;//Total price int cmp(station a,station b) { return a.dis<b.dis; } int func(int now) { int index=wrong;//next for(int i=now+1;i<=n&&st[i].dis-st[now].dis<=maxn;i++)//Find the gas station you can find { if(st[i].price<st[now].price)//Can you get & & cheap { price_sum+=(st[i].dis-st[now].dis)/d2*st[now].price; res=0; return i; } if(index==wrong||st[i].price<st[index].price) index=i;//Yes, it's not cheap } if(d1-st[now].dis<=maxn)//There is no cheaper one, and we can reach the end { price_sum+=(d1-st[now].dis-res)/d2*st[now].price; return wrong; } if(index==wrong) { //I can't get to the next stop cout<<"No Solution"<<endl; return -1; } else//There's no cheaper one, and you can't get to the end all at once { price_sum+=c*st[now].price; res+=(maxn-(st[index].dis-st[now].dis)); return index; } } int main() { cin>>d1>>c>>d2>>p>>n; st[0].dis=0; st[0].price=p; for(int i=1;i<=n;i++) { cin>>st[i].dis>>st[i].price; } sort(st,st+n+1,cmp); now=0; maxn=c*d2; do { t=func(now); now=t; if(t==-1) return 0; }while(t!=wrong); cout<<fixed<<setprecision(2)<<price_sum<<endl; return 0; }

Hu ~ I thought greedy algorithm was much simpler than dynamic programming. Unexpectedly, this problem took me a long time

It's a little messy in thinking and writing. I hope you can understand it~