To Fill or Not to Fill

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
struct gas_stations
{
    double pi;
    int di;
};
bool compare(gas_stations g1, gas_stations g2)
{
    return g1.pi < g2.pi;
}
int main()
{
    int C, D, Davg, N;
    double cost;
    while (cin>>C>>D>>Davg>>N)
    {
        gas_stations* G = new gas_stations[N];
        for (int i = 0; i < N; i++)//输入加油站位置、价格
            cin >> G[i].pi >> G[i].di;

        sort(G, G + N,compare);//按价格排序

        cost = 0;//记录花费
        int max = C * Davg, need, dis;
        int* flag = new int[D+10];
        memset(flag, 0, (D + 10) * sizeof(int));
        //关键代码
        for (int i = 0; i < N; i++)
        { //如果到终点距离<max,只需加上足够走到终点的油
            need = (G[i].di + max < D ? max : D - G[i].di);    
            dis = 0;    //记录有多长距离需要该加油站的油
            for (int j = G[i].di; j < G[i].di + need; j++)
            {
                if (flag[j] == 0)
                {
                    flag[j] = 1;
                    dis++;
                }
            }
            cost += dis / (Davg * 1.0) * G[i].pi; //加上在该加油站的花销
        }
        //输出
        cout.precision(2);
        int i;
        for (i = 0; i < D; i++)
        {//有的路程没有被覆盖到说明走不到这里
            if (flag[i] == 0)
            {
                cout << "The maximum travel distance = " <<fixed<< (double)i << endl;
                break;
            }
        }
        if (i == D)//到达目的地
            cout <<fixed<< cost << endl;
        delete[] G, flag;
    }
    return 0;
}

#define _CRT_SECURE_NO_WARNINGS
(842)#include <algorithm>
using namespace std;

const int MAXN = 500 + 10;

struct Station_t {
	double price;
	double dest;
	double cov;//最远能覆盖到的坐标点
	bool operator<(const Station_t x) {
		return dest < x.dest;
	}
};
Station_t gStation[MAXN];

int main() {
	int capacity, dest, davg, n;
begin:
	while (scanf("%d%d%d%d", &capacity, &dest, &davg, &n) != EOF) {
		double eDest = (double)capacity * davg;//eDest表示每次油箱装满能走得最远距离
		for (int i = 0; i < n; i++) {
			scanf("%lf%lf", &gStation[i].price, &gStation[i].dest);
			gStation[i].cov = gStation[i].dest + eDest;
		}
		gStation[n].dest = dest;
		gStation[n].price = 0;
		sort(gStation, gStation + n);
		for (int i = 0; i < n; i++) {//判断最终能否到达加油站
			if (gStation[i].cov < gStation[i + 1].dest) {
				printf("The maximum travel distance = %.2lf\n", gStation[i].cov);
				goto begin;
			}
		}
		int index = 0, nextIndex = 0;//index表示当前所在加油站的标识
		double cost = 0, curMass = 0, needMass;//成本、当前油量、到达下一站需要的油量
		while (index < n) {
			double minPrice = gStation[index].price;
			nextIndex = index;
			//找油箱加满后能够行驶的距离范围内比当前加油站油价便宜的最近的加油站
			for (int i = index + 1; i <= n && gStation[i].dest <= gStation[index].cov; i++) {
				if (gStation[i].price <= minPrice) {
					minPrice = gStation[i].price;
					nextIndex = i;
					break;
				}
			}
			//如果找到了可行驶距离范围内比当前所在加油站拥有更低油价的加油站，那么只需要使油量够行驶至此加油站即可
			if (nextIndex != index) {//找到了更便宜的油站
				needMass = (gStation[nextIndex].dest - gStation[index].dest) / davg;//行驶到此站需要的油量
				if (curMass < needMass) {//查看油量是否够用,不够用则加油至刚好能到这一站
					cost += (needMass - curMass) * gStation[index].price;
					curMass = 0;//到达下一站，油量刚好归零
				}
				else {//油量够用，不用再额外加油
					curMass -= needMass;
				}
				index = nextIndex;
			}
			else {//没有找到价格更低的加油站，把油加满，走到下个加油站
				cost += (capacity - curMass) * gStation[index].price;
				curMass = capacity;
				needMass = (gStation[index + 1].dest - gStation[index].dest) / davg;
				curMass -= needMass;
				index++;
			}
		}
		printf("%.2lf\n", cost);
	}
	return 0;
}

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
struct station{
    double p;//单位油价格（不同）
    double d;//本站和杭州之间的距离
};
bool cmp(station x,station y){
    if(x.d==y.d)//距离相同比价格
        return x.p<y.p;
    else
        return x.d<y.d;
}
int main(){//不要用float，全部double
    double Cmax;//油箱最大容量
    double D;//杭州和目的城市之间的距离
    double Davg;//单位***驶里程（相同）
    int n;//加油站的总数
    while(cin>>Cmax>>D>>Davg>>n){
        station sta[n+1];
        for(int i=0;i<n;i++)
            cin>>sta[i].p>>sta[i].d;
        sta[n].p=0,sta[n].d=D;//增加终点站
        sort(sta,sta+n,cmp);
        double cap=0;//剩余油量
        double x=0;//行驶总里程
        double price=0;//总油费
        double Dmax=Cmax*Davg;//满油最大里程
        for(int i=0;i<n;i++){
            if(Dmax<(sta[i+1].d-sta[i].d)){//加满油也到不了下一站
                printf("The maximum travel distance = %.2f\n",x+Dmax);//输出最大行驶历程
                break;
            }
            int cheapest=i+1;//标记油价最便宜的站
            int nearest=i+1;//标记便宜且距离最近的站 
            int pmin=sta[i+1].p;//标记前方最低油价 
            for(int j=i+1;Dmax>=(sta[j].d-sta[i].d)&&j<=n;j++){//在所能到达的所有加油站中（包括终点站） 
                if(sta[j].p<=pmin){//寻找油价最便宜的站
                    cheapest=j;
                    pmin=sta[j].p;
                }
            }
            for(int j=i+1;Dmax>=(sta[j].d-sta[i].d)&&j<=n;j++){//在所能到达的所有加油站中（包括终点站） 
                if(sta[j].p<=sta[i].p){//寻找便宜且距离最近的站
                    nearest=j;
                    break;
                }
            }
            if(sta[i].p<pmin){//当前站油价最便宜，加满油去下一个油价最便宜的站 
                price=price+(Cmax-cap)*sta[i].p;//油费++
                cap=Cmax;//加满
                x=x+sta[cheapest].d-sta[i].d;//里程++
                cap=cap-(sta[cheapest].d-sta[i].d)/Davg;//油量--
                i=cheapest-1;//i++-->cheapest
            }
            else{//前面有油价小于或等于当前油价的站，视情况加油去距离最近的便宜站 
                if(cap*Davg<(sta[nearest].d-sta[i].d)){//如果剩余油到不了最近便宜站
                    price=price+((sta[nearest].d-sta[i].d)/Davg-cap)*sta[i].p;//油费++
                    cap=(sta[nearest].d-sta[i].d)/Davg;//加刚好能到最近便宜站的油
                }
                x=x+sta[nearest].d-sta[i].d;//里程++
                cap=cap-(sta[nearest].d-sta[i].d)/Davg;//油量--
                i=nearest-1;//i++-->nearest
            }
            
        }
        if(x==D)//到达终点站
            printf("%.2f\n",price);
    }
    return 0;
}

/*
核心思路:利用贪心策略,从最便宜的加油站开始,每个加油站加的油最多能走cmax*davg路程.
利用一个30000大小的flag数组记录是否有重合区域
*/
#include<cstdio>
#include<algorithm>
using namespace std;

struct sta{
    double pi;
    int di;
    bool operator < (const sta& b) const{
        return pi<b.pi;
    }
}a[501];

int main(){
    int cmax, d, davg, n;
    double sum;
    while(scanf("%d %d %d %d", &cmax, &d, &davg, &n)!=EOF){
        for(int i=0; i<n; i++) scanf("%lf %d", &a[i].pi, &a[i].di);
        sort(a, a+n);
        //
        sum = 0;//记录花费
        int flag[30001]={0}, max = cmax*davg, tmp, cnt;
        for(int i=0; i<n; i++){
            tmp = (a[i].di+max<d?max:d-a[i].di);    //如果到终点距离<max,只需加上足够走到终点的油
            cnt = 0;    //记录有多长距离需要该加油站的油
            for(int j=a[i].di; j<a[i].di+tmp; j++){
                if(flag[j]==0){
                    flag[j] = 1;
                    cnt++;
                }
            }
            sum += cnt/(davg*1.0)*a[i].pi;    //加上在该加油站的花销
        }
        //check
        int i;
        for(i=0; i<d; i++){
            //有的路程没有被覆盖到说明走不到这里
            if(flag[i]==0){
                printf("The maximum travel distance = %.2lf\n", (double)i);
                break;
            }
        }
        if(i==d){
            printf("%.2lf\n",sum);
        }
    }
    return 0;
}

#include<stdio.h>
#include<algorithm>
using namespace std;
typedef struct station{
    double price;
    double dis;
    bool operator <(const station &A) const {
        return dis<A.dis;
    }
}station;
int main(){
    station buf[501];
    int i,j,n;
    double cmax,d,davg,maxdis,ans;
    while(scanf("%lf%lf%lf%d",&cmax,&d,&davg,&n)!=EOF){
        ans=0;
        maxdis=cmax*davg;
        for(i=0;i<n;i++)
            scanf("%lf%lf",&buf[i].price,&buf[i].dis);
        buf[n].dis=d;
        sort(buf,buf+n);
        if(buf[0].dis!=0){
            printf("The maximum travel distance = 0.00\n");
            continue;
        }
        double curpos=0;
        double curoil=0;
        for(i=0;i<n;i++){
            curpos=buf[i].dis;
            if(curpos+maxdis<buf[i+1].dis){
                printf("The maximum travel distance = %.2lf\n",curpos+maxdis);
                break;
            }
            if(i>0)
                curoil-=(buf[i].dis-buf[i-1].dis)/davg;
            double curdis=0;
            bool ischeap=false;
            for(j=i+1;j<n;j++){
                curdis=buf[j].dis-buf[i].dis;
                if(curdis>maxdis) break;
                if(buf[j].price<buf[i].price){
                    double temp=(buf[j].dis-buf[i].dis)/davg;
                    if(temp>curoil){
                        ans+=(temp-curoil)*buf[i].price;
                        curoil=temp;
                    }
                    ischeap=true;
                    break;
                }
            }
            if(!ischeap){
                if(curpos+maxdis>=d){
                    ans+=((d-curpos)/davg-curoil)*buf[i].price;
                    printf("%.2lf\n",ans);
                    break;
                }
                else{
                    ans+=(cmax-curoil)*buf[i].price;
                    curoil=cmax;
                }
            }
        }
    }
    return 0;
} 

在网上看了一些思路才会做这题，利用贪心算法，每次走一个加油站，记录当前的距离和油量，
然后查看最大距离以内的加油站有没有比当前站便宜的，若有，则查看油量，
把油量加到足够到达便宜的站，若没有，则看油量够不够到终点，不够则把油加满。
在到达没站的过程中若油量不够到达最近的一站，则输出最大距离。
特殊情况：没有距离为0的加油站。
结果实现过程中没想到漏掉一个换行符和一个break弄了我很长时间。
给的测点又看不完全。心塞。。。

/*
    说下思路，这题写了我一天
    贪心的思想，我们将终点看做一个价格为0,距离为最大值的车站
    读入所有车站，按照距离从小到大排序，如果距离相同，按照价格从小到大，因为距离相同的油站我们取最便宜的
    然后默认我们从起始的位置，也就是0起点的油站开始走
    特殊情况：
        如果起始点没有油站，那么车无法走，直接认为无解。

    从当前车站往后搜寻比当前油站价格便宜的。
        1.如果有比当前价格便宜的，那么加油到能够开到这个油站，然后继续寻找下一个更便宜的油站
        2.如果没有，那么记录能够到达的油站中相对价格最低的，认为从当前油站加满油直接开到这个油站
        这个很重要，就是因为这个问题卡了我一整天
        3.如果没有找到比当前价格便宜的油站并且也没找到相对价格便宜的油站，那就退出，用当前油站的距离加上
        满油能走的最大距离，输出
    
*/
#include <bits/stdc++.h>
using namespace std;
struct station{
	double price,dis;
};
bool cmp(station a,station b){
	if(a.dis==b.dis){
		return a.price<b.price;
	}else{
		return a.dis < b.dis;
	}
}

const double inf = 999999999;

int main(){
	double cmax,d,davg;
	int n;
	cin>>cmax>>d>>davg>>n;
	station sta[n+1];
	sta[0].price = 0;sta[0].dis = d;
	for(int i=1;i<=n;i++){
		cin>>sta[i].price>>sta[i].dis;
	}
	sort(sta,sta+n+1,cmp);
	double nowprice = 0.0,nowdis = 0.0;
	double totalprice = 0.0,leftdis = 0.0; // leftdis 用于表示当前最便宜的油还能走多久 
	if(sta[0].dis!=0){
		cout<<"The maximum travel distance = 0.0";
		return 0;
	}else{
		nowprice = sta[0].price;
	}
	while(nowdis!=d){
		double maxdis = cmax*davg+nowdis; // 当前满油能走多远  
		double minprice = inf;
		double minpriceDis = 0.0;
		int flag = 0;
		for(int i=1;i<=n&&sta[i].dis<=maxdis;i++){
			if(sta[i].dis<=nowdis){ // 若油站已经走过 
				continue; 
			}else{
				if(sta[i].price<nowprice){ // 找到比当前价格便宜的油站 
					flag = 1;
					totalprice += (sta[i].dis-nowdis-leftdis)/davg * nowprice;
					leftdis = 0.0;
					nowdis = sta[i].dis;
					nowprice = sta[i].price;
					break;
				}else if(sta[i].price<minprice){ // 记录当前可以到达的价格相对较小的油站 
					minprice = sta[i].price;
					minpriceDis = sta[i].dis;
				}
			} 
		}
		if(flag == 0 && minprice != inf){ // 未找到比当前价格便宜的油站,但是有相对便宜的
			totalprice += (nowprice * (cmax - leftdis/davg));
			leftdis = cmax*davg+nowdis - minpriceDis; // 计算便宜的=又还能走多远
			nowprice = minprice;
			nowdis = minpriceDis;
		}
		if(flag == 0 && minprice == inf){ // 未找到比当前便宜的油站并且也不能找到最便宜的 
			printf("The maximum travel distance = %.2f",maxdis);
			return 0;
		}
	}
	printf("%.2f\n",totalprice);
	return 0;
}

• 输入：邮箱容量Cmax_终点距离D_每升油能跑Davg_加油站数量N
•             N组{油价Pi_加油站距起点Di}
  
• 输出：1.最低花费cost（能跑到终点）
•             2.“The maximum travel distance = xx.xx”（跑不到终点）
  
• 思路：1.准备阶段------------------
•     数据结构：struct Station{    double price, distance; }st[MAXN]；//尽量用浮点型，防止被坑
  
•     变量：将终点当作最后一站：st[N].distance = D; st[N].price = 0.0;
  
•                 满油状态能跑最远距离：maxRun = Cmax * Davg
  
•                 全程花费：cost = 0.0
  
•                 到达某一站时所剩油量：nowGas = 0.0
  
•                 从 i 站到 j 站所需油量：needGas = (Dj - Di)/Davg
  
•                 实际加油量：addGas = needGas - nowGas
•             2.读取处理数据--------------
  
•             读取全部数据，并以路程从小到大排序
  
•             3.最优策略--------------------
  
•             判断在i号加油站时，是否能以满油状态可达到i+k号站？
  
•             若k = 0 则无法到达下一站，此次航程最多为Di + maxRun【输出1】
  
•             否则：
  
•                     若能找到比i号站油价更低的最近加油站j：needGas = (Dj-Di)/Davg
•                     （抓紧去那个便宜的地方加油）
•                     |    倘若当前油量nowGas >= needGas 时，说明剩余油量充足，不需要加油；
  
•                     |    |        到达j站后，剩余油量nowGas = nowGas - needGas
  
•                     |    但油不够时，需要加油addGas = needGas - nowGas;到达j站后，nowGas  = 0.0;
  
•                     |            且花费了 cost += addGas * Pi;
  
•                     但找不到的话，就退而求其次找个油价最低的：needGas = (Dj-Di)/Davg
•                    （虽然比i站高点，但还能接受，所以先在i站加满油，这样才不吃亏）
  
•                             直接加满油 addGas = Cmax - nowGas; 花了：cost +=addGas * Pi
•                             到达j站后，nowGas = Cmax - needGas;
  
•             最后令 i = j，即以j站开始，继续循环，直到终点站。
  
•             4.输出----------------cost
  
• 代码：
• #include "stdafx.h"
  #include <cstdio>
  #include <algorithm>
  using namespace std;
  const int MAXN = 510;
  struct station{
      double price, distance;
  }st[MAXN];
  bool cmp(struct station a, struct station b){
      return a.distance < b.distance;
  }
  int main(){
      double Cmax, D, Davg;    int N;
      scanf("%lf%lf%lf%d", &Cmax, &D, &Davg, &N);
      for(int n = 0; n < N; ++n){
          scanf("%lf%lf", &st[n].price, &st[n].distance);
      }
      st[N].price = 0.0;st[N].distance = D;
      double maxRun = Cmax * Davg, cost = 0.0, nowGas = 0.0, addGas = 0.0, needGas = 0.0;
      sort(st, st + N, cmp);
      if(st[0].distance != 0){printf("The maximum travel distance = 0.00");return 0;}
      int i = 0;
      while(i < N){
          int k = 0;
          while(i+k <= N && st[i+k].distance - st[i].distance <= maxRun){
              k++;
          }
          k--;
          if(k <= 0){printf("The maximum travel distance = %.2f\n", st[i].distance + maxRun); return 0;}
          int j;
          for(j = i; j <= i + k; ++j){
              if(st[j].price < st[i].price)break;
          }
          if(j <= i + k){
              needGas = (st[j].distance - st[i].distance)/Davg;
              if(nowGas >= needGas)nowGas -= needGas;
              else{addGas = needGas - nowGas; nowGas = 0.0; cost += addGas * st[i].price;}
          }else{
              j = i + 1;
              for(int tmp = i + 1; tmp <= i + k; ++tmp)
                  if(st[tmp].price < st[j].price)j = tmp;
              needGas = (st[j].distance - st[i].distance)/Davg;
              addGas = Cmax - nowGas;
              nowGas = Cmax - needGas;
              cost += addGas * st[i].price;
          }
          i = j;
      }
      printf("%.2f\n", cost);
      return 0;
  }
  
  

package com.speical.first;

import java.util.Scanner;
/** 
* 加油站问题
* 
* 这不能用背包来做，因为情况非常复杂
* 因为到每个加油站的状态并不是固定，因为不是每次都到加油不是把油正好加到下一个加油站
* 所以我们采用贪心的做法
* 情况如下：
* 1.刚开始，我们的车没油，所以要找0距离油价最少的那一个
* 2.然后考察车的最大距离里的所有加油站，看看是否有比当前油价少的加油站
*     1.若有，我们只需加油加到正好到该加油站即可，因为之后的距离我想用便宜的油价
*   2.若没有，我们只能在找到最大距离内大于当前油价最小的那一个即可，但是此时我们要
*   把油加满，因为当前油价便宜啊，加满之后，到大于当前油价最小的那一个的加油站时，继续考察
*   到的那个加油站即可。之后我们要再次根据距离，补充油（注意此时油箱是有油的，上次油价便宜）。
*   
* 以上在油价时，我们用leftdis表示油箱中剩余的油能走的距离，所以在根据距离算钱，要减去该距离
* @author special
* @date 2018年1月29日 上午11:40:18
*/
public class Pro152 {

    static double Cmax, D, Davg, onceMaxDis;
    static int N;
    static final double MIN = Double.MAX_VALUE;

    static class Node{
        double price;
        double dis;

        public Node(double price, double dis){
            this.price = price;
            this.dis = dis;
        }
    }
    private static boolean less(Node node1, Node node2){
        if(node1.dis < node2.dis || node1.dis == node2.dis
                                 && node1.price < node2.price){
            return true;
        }
        return false;
    }

    public static void insertSort(Node[] nodes, int n){
        for(int i = 1; i < n; i++){
            for(int j = i; j > 0 && less(nodes[j], nodes[j - 1]); j--){
                Node temp = nodes[j];
                nodes[j] = nodes[j - 1];
                nodes[j - 1] = temp;
            }
        }
    }

    public static void solution(Node[] nodes){
        boolean flag = true;
        int index = 0;
        double nowPerPrice, nowDis = 0, maxDis, totalPrice = 0, 
               leftDis = 0, minPrice = MIN, minDis = 0;
        while(nodes[index].dis == 0){  //找0距离的最小的油价的加油站
            minPrice = Math.min(minPrice, nodes[index].price);
            index++;
        }
        if(index == 0){ //若没有，说明没法走
            flag = false;
        }else{
            nowPerPrice = minPrice;  //更新当前的油价
            boolean isShorter = false; //是否存在比当前油价小的加油站
            while(nowDis < D){
                maxDis = nowDis + onceMaxDis; //当前能到的最大位置
                minPrice = MIN; 
                minDis = 0;
                isShorter = false;
                for(int i = index; i <= N && nodes[i].dis <= maxDis; i++){
                    if(nodes[i].dis == nowDis) continue;
                    if(nodes[i].price < nowPerPrice){  //因为我们排序的缘故，保证了大于当前位置的第一个加油站必是同位置的最小的
                        totalPrice += nowPerPrice * (nodes[i].dis - nowDis - leftDis) / Davg; //注意要减去油箱中剩余的油
                        nowPerPrice = nodes[i].price;
                        nowDis = nodes[i].dis;
                        leftDis = 0;
                        isShorter = true;
                        index = i;
                        break; //直接跳出即可，同位置之后的油价肯定是大于等于当前的
                    }
                    if(nodes[i].price < minPrice){ //我们还要记录最大距离的最小的油价，万一我们找不到更实惠，就可以将就一下
                        minPrice = nodes[i].price;
                        minDis = nodes[i].dis;
                        index = i;
                    }
                }
                if(!isShorter){ // 真没有比当前更实惠的
                    if(minPrice == MIN){ //油价还是天价，说明我们的车不行，跑不到加油站
                        nowDis += onceMaxDis; //在当前的加油站，加满，跑完得了，因为车不行
                        flag = false;
                        break;
                    }else{
                        totalPrice += nowPerPrice * (onceMaxDis - leftDis) / Davg; //否则就是我们加满油，跑到还可以接受的加油站
                        leftDis = onceMaxDis - (minDis - nowDis); //跑到那里之后，我们会剩余多少油
                        nowDis = minDis;
                        nowPerPrice = minPrice;
                    }
                }
            }
        }
        if(flag){
            System.out.format("%.2f\n", totalPrice);
        }else{
            System.out.format("The maximum travel distance = %.2f\n", nowDis);
        }
    }
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        while(input.hasNext()){
            Cmax = input.nextDouble();
            D = input.nextDouble();
            Davg = input.nextDouble();
            N = input.nextInt();

            Node[] nodes = new Node[N + 1];
            onceMaxDis = Cmax * Davg;  //油箱满的时候，走的最大距离

            for(int i = 0; i < N; i++){
                nodes[i] = new Node(input.nextDouble(), input.nextDouble());
            }
            nodes[N] = new Node(0, D);
            insertSort(nodes, N + 1); // 插入排序，为了减少内循环的次数
            solution(nodes);
        }
    }
}

#include <iostream>
#include <algorithm>
#include <iomanip>

using namespace std;

struct gasT{
    double price;
    int  pos;
};

bool compareByPos(gasT a,gasT b){
    if(a.pos==b.pos){
        return a.price<b.price;//位置相同以油价升序排列
    }else{
        return  a.pos<b.pos;//以位置升序排列
    }

}
int main() {
    int capacity, TotalDistance, DistancePerGas, GasTnum;
    while (cin >> capacity >> TotalDistance >> DistancePerGas >> GasTnum) {
            gasT pos[GasTnum+1];
            for (int i = 0; i < GasTnum; ++i) {
                cin >> pos[i].price >> pos[i].pos;
            }
            sort(pos, pos + GasTnum, compareByPos);

            pos[GasTnum].price=0;//把终点设为加油站
            pos[GasTnum].pos=TotalDistance;

            //贪心思路：每到一个加油站向后查询一个满油能跑距离内是否有比目前油价便宜的最近加油站（加油至足够到达该目的加油站
            //结束条件：终点距离加油站满油距离内，距离内部的加油站价格都比目前高，加油至终点，结束查询，输出消费
            int fullGasRun = capacity * DistancePerGas;//满油能跑的距离
            double leftRun = 0;//还能跑多远
            double spend = 0;//目前消费
            double run = 0;//目前走了多远
            int t = 0;//目前到的加油站-1（以距离起点位置升序排号）

            while(t<GasTnum+1){
                if(pos[0].pos!=0){//起点没有加油站，退出输出
                    cout << "The maximum travel distance = " << 0.00 << endl;
                    break;
                }
                int cheap=0;
                for(int j=t+1;pos[j].pos-pos[t].pos<=fullGasRun;j++){//1.位置要在满油距离内//在目前的加油站向后遍
                        if(pos[t].price >= pos[j].price){//2.找比目前便宜的第一个加油站（一样价格也可以）
                            if(leftRun<pos[j].pos - pos[t].pos){//余油不足，把油加到刚好够到达便宜加油站的量即可
                                spend = (pos[j].pos - pos[t].pos - leftRun)* pos[t].price /DistancePerGas+spend;
                                leftRun =  pos[j].pos - pos[t].pos;
                            }
                            run += pos[j].pos - pos[t].pos;//余油充足与否都需要的操作
                            leftRun = leftRun -pos[j].pos + pos[t].pos;
                            t=j;
                            cheap=1;
                            break;//退出for的小循环
                        }
                }
                if(leftRun+pos[t].pos>=TotalDistance){//可到达终点，输出
                    cout << fixed << setprecision(2) << spend << endl;
                    break;
                }
                if(cheap==0){//没有便宜的加满
                    spend += (fullGasRun - leftRun) / DistancePerGas * pos[t].price;
                    leftRun = fullGasRun;
                }else{
                    continue;//找到便宜的加油站就不执行下面的操作
                }
                if(pos[t+1].pos-pos[t].pos>fullGasRun){//下一个油站不在满油距离内(把leftrun清空)
                    run+=leftRun;
                    cout<< fixed << setprecision(2) << "The maximum travel distance = "<< run << endl;
                    break;
                }
                t++;//走到下一个加油站
                leftRun-= pos[t].pos-pos[t-1].pos;
                run+=pos[t].pos-pos[t-1].pos;
            }
        }
    }

#include <bits/stdc++.h>
using namespace std;

double dp[30005];

struct station {
    double price;
    int dis;
};

bool cmp(station a, station b) {
    return a.dis < b.dis;
}
int main() {
    int Cmax, D, Davg, N;
    while (cin >> Cmax >> D >> Davg >> N) { // 注意 while 处理多个 case
        for (int i = 0; i <= D; i++) dp[i] = INT_MAX;
        int maxlen = Cmax * Davg;

        vector<station> v;
        while (N--) {
            station tmp;
            cin >> tmp.price >> tmp.dis;
            v.push_back(tmp);
        }
        sort(v.begin(), v.end(), cmp);
        for (int i = 0; i < v.size(); i++) {
            int start = v[i].dis;
            double price = v[i].price;
            for (int j = 1; j <= maxlen; j++) {
                dp[start + j] = min(dp[start + j], price);
            }
        }
        double price = 0;
        int flg = 1;
        for (int i = 1; i <= D; i++) {
            if (dp[i] == INT_MAX) 
            {
                flg = 0;
                cout <<"The maximum travel distance = "<<
                fixed<<setprecision(2)<< (i - 1)*1.0 << endl;
                break;
            }
            price+=dp[i];
        }
        if(flg) cout<<fixed<<setprecision(2)<<price/Davg<<endl;

    }
}