B1033 To Fill or Not to Fill (25分)

//模拟加油站加油问题，决策很关键

print The maximum travel distance = X where X is the maximum possible distance the car can run, accurate up to 2 decimal places.
//注意路程，加油，还有油费都是double类型

• 结构体按距离从小到大排序
• 从当前点出发所能到达的最大距离里挑点
• 如果有最近的点油费低于当前点，那就把油加到刚好能到达那个点
• 如果范围内的点的油费都大于当前点，则需要把当前点的油费加满。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string.h>
#include <cmath>
#include <math.h>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stack>
#define lowbit(i)((i)&(-i))
using namespace std;
typedef long long ll;
const int MAX=10005;
const int INF=0x3f3f3f3f;
const int MOD=1000000007;
const int SQR=633;
struct node
{
    double price;
    double dis;
}sta[MAX];
bool cmp(node a,node b)
{
    return a.dis<b.dis;
}
int main()
{
    double cmax,d,davg;
    int n;
    scanf("%lf%lf%lf%d",&cmax,&d,&davg,&n);
    for(int i=0;i<n;i++)
    {
        scanf("%lf%lf",&sta[i].price,&sta[i].dis);
    }
    sta[n].price=0;
    sta[n].dis=d;
    sort(sta,sta+n,cmp);
    if(sta[0].dis!=0)
    {
        printf("The maximum travel distance = 0.00\n");
    }
    else
    {
        int now=0;
        double ans=0.0,nowtank=0.0;
        double maxdis=cmax*davg;
        while(now<n)//起点之后
        {
             double minprice=INF;
             int k=-1;
             for(int i=now+1;i<=n&&sta[i].dis-sta[now].dis<=maxdis;i++)
             {
                 if(sta[i].price<minprice)
                 {
                     minprice=sta[i].price;
                     k=i;
                     if(sta[now].price>sta[k].price)
                     {
                         break;
                     }
                 }
             }
             if(k==-1)
             {
                 break;
             }
             double need=(sta[k].dis-sta[now].dis)/davg;
             if(sta[k].price<sta[now].price)
             {
                 if(nowtank<need)
                 {
                     ans+=(need-nowtank)*sta[now].price;
                     nowtank=0;
                 }
                 else
                     nowtank-=need;
             }
             else
             {
                 ans+=(cmax-nowtank)*sta[now].price;
                 nowtank=cmax-need;
             }
             now=k;
        }
        if(now==n)
        {
            printf("%.2f\n",ans);
        }
        else
        {
            printf("The maximum travel distance = %.2f\n",sta[now].dis+maxdis);
        }
    }
   return 0;
}