A1033 To Fill or Not to Fill (25 point(s))

贪心

1. 原文

原题

With highways available, driving a car from Hangzhou to any other city is easy. But since the tank capacity of a car is limited, we have to find gas stations on the way from time to time. Different gas station may give different price. You are asked to carefully design the cheapest route to go.

Input Specification:

Each input file contains one test case. For each case, the first line contains 4 positive numbers: Cmax (≤ 100), the maximum capacity of the tank; D (≤30000), the distance between Hangzhou and the destination city; Davg (≤20), the average distance per unit gas that the car can run; and N (≤ 500), the total number of gas stations. Then N lines follow, each contains a pair of non-negative numbers: $P_i$, the unit gas price, and $D_i$ (≤D), the distance between this station and Hangzhou, for i=1,⋯,N. All the numbers in a line are separated by a space.

output Specification:

For each test case, print the cheapest price in a line, accurate up to 2 decimal places. It is assumed that the tank is empty at the beginning. If it is impossible to reach the destination, print The maximum travel distance = X where X is the maximum possible distance the car can run, accurate up to 2 decimal places.

Sample Input 1:

50 1300 12 8
6.00 1250
7.00 600
7.00 150
7.10 0
7.20 200
7.50 400
7.30 1000
6.85 300

Sample output 1:

749.17

Sample Input 2:

50 1300 12 2
7.10 0
7.00 600

Sample output 2:

The maximum travel distance = 1200.00

2. AC代码

#include<cstdio>
#include<algorithm>
using namespace std;
const int Inf = 1<<30;
struct node{
	double price,dis;
}station[510];
bool cmp(node a,node b){
	return a.dis<b.dis;
}
int main(){
	double cmax,d,avg;
	int n;
	scanf("%lf%lf%lf%d",&cmax,&d,&avg,&n);
	for (int i = 0; i < n; ++i)
	{
		scanf("%lf%lf",&station[i].price,&station[i].dis);
	}
	station[n].price = 0;
	station[n].dis = d;
	sort(station,station+n,cmp);
	if (station[0].dis!=0)
	{
		printf("The maximum travel distance = 0.00\n");
	}else{
    //加油站编号
    int now = 0;
    //满油行驶距离
    double max = cmax*avg;
    //当前油量
    double nowTank = 0;
    //总花费
    double ans = 0;
		while(now<n){
			int k = -1;
			double minPrice = Inf;
			for(int i = now+1;i<=n&&station[i].dis-station[now].dis<=max;i++){
				if(station[i].price<minPrice){
					minPrice = station[i].price;
					k = i;
				}
        //找到小于当前油价的加油站
				if (minPrice<station[now].price)
				{
					break;
				}
 
			}
			if (k==-1)
			{
				break;
			}
      //从now到k需要的油量
			double need = (station[k].dis-station[now].dis)/avg;
			if (minPrice<station[now].price)
			{
        //油不够
				if (nowTank<need)
				{
          //买到k站的油量
					ans+=(need-nowTank)*station[now].price;
          //到达k后油量为0
					nowTank=0;
				}else{
					nowTank-=need;
				}
			}else{
        //k的油价高于now，直接加满
				ans+=(cmax-nowTank)*station[now].price;
        //到达k后油量为cmax-need
				nowTank = cmax-need;
			}
			now = k;
		}
		if (now==n)
		{
			printf("%.2f\n", ans);
		}else{
			printf("The maximum travel distance = %.2f\n",station[now].dis+max);
		}
	}
	
	return 0;
}