PAT甲級1033

1033. To Fill or Not to Fill (25)

時間限制

10 ms

記憶體限制

65536 kB

代碼長度限制

16000 B

判題程式

Standard

作者

ZHANG, Guochuan

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: Pi, the unit gas price, and Di (<=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

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 510;
const int INF = 1000000000;
struct station
{
  double price, dis;//價格、與起點的距離
}st[maxn];
bool cmp(station a, station b)
{
  return a.dis < b.dis;//按距離從小到大
}
int main()
{
  int n;
  double Cmax, D, Davg;
  scanf("%lf%lf%lf%d", &Cmax, &D, &Davg, &n);
  for (int i = 0; i < n; i++)
  {
    scanf("%lf%lf", &st[i].price, &st[i].dis);
  }
  st[n].price = 0;//數組最後面放置終點，價格為0
  st[n].dis = D;//終點距離為D
  sort(st, st + n, cmp);//将所有加油站按距離從小到大排序
  if (st[0].dis != 0)//如果排序後的第一個加油站距離不是0，說明無法前進
  {
    printf("The maximum travel distance = 0.00\n");
  }
  else
  {
    int now = 0;//目前所處的加油站編号
    //總花費、目前油量及滿油行駛距離
    double ans = 0, nowTank = 0, MAX = Cmax*Davg;
    while (now < n)//每次循環選出下一個需要加油的站
    {//選出從目前加油站滿油能到達範圍内的第一個油價低于目前油價的加油站
      //如果沒有低于目前油價的加油站，則選擇價格最低的那個
      int k = -1;//最低油價的加油站的編号
      double priceMin = INF;//最低油價
      for (int i = now + 1; i <= n&&st[i].dis - st[now].dis <= MAX; i++)
      {
        if (st[i].price < priceMin)//如果油價比目前最低油價低
        {
          priceMin = st[i].price;//更新最低油價
          k = i;
          //如果找到第一個油價低于目前油價的加油站，直接中斷循環
          if (priceMin < st[now].price)
          {
            break;
          }
        }
      }
      if (k == -1)break;//滿油狀态下無法找到加油站，退出循環輸出的結果
      //下面為能找到可到達的加油站k，計算轉移花費
      //need為從now到k需要的油量
      double need = (st[k].dis - st[now].dis) / Davg;
      if (priceMin < st[now].price)//如果加油站k的油價低于目前油價
      {
        //隻買足夠到達加油站k的油
        if (nowTank < need) {//如果目前油量不足need
          ans += (need - nowTank)*st[now].price;//補足need
          nowTank = 0;//到達加油站k後油箱内油量為0

        }
        else//如果目前油量超過need
        {
          nowTank -= need;//直接到達加油站k  
        }
      }
      else//如果加油站k的油價高于目前油價
      {
        ans += (Cmax - nowTank)*st[now].price;//将油箱加滿
        //到達加油站k後油箱内油量為Cmax-need
        nowTank = Cmax - need;
      }
      now = k;//到達加油站k，進入下一層循環
    }
    if (now == n)//能到達終點
    {
      printf("%.2f\n", ans);
    }
    else//不能到達終點
    {
      printf("The maximum travel distance = %.2f\n", st[now].dis + MAX);
    }
  }
  return 0;
}