//贪心算法解决加油站选择问题//# include<iostream># include<stdio.h>using namespace std;# include<algorithm>struct Node{    float p, d;};bool cmp(Node a, Node b){    return a.d < b.d;}int main(){    Node node[501];    float Cmax, D, Davg, distance, price, Ccur, Pcur, j;//double 会出问题，蛋疼    int N, Ncur, i, k, flag;    //while (cin >> Cmax >> D >> Davg >> N)    while (scanf_s("%f%f%f%d", &Cmax, &D, &Davg, &N) != EOF)    {        for (i = 1; i <= N; i++)        {            //cin >> node[i].p >> node[i].d;            scanf_s("%f%f", &node[i].p, &node[i].d);        }        //sort station by distance          sort(node + 1, node + 1 + N, cmp);                if (N == 0 || node[1].d > 0.00001 || node[1].d < -0.00001)//第一个站点不在距离0处        {            printf("The maximum travel distance = 0.00\n");        }        else//greedy now        {            price = 0;//当前花费            distance = 0;//当前距离            Ncur = 1;//当前所在加油站            Ccur = 0;//当前汽油数量            Pcur = node[1].p;//当前加油站的油价            while (Ncur <= N)            {                //1.using 【remain】 gas find 【nearest】 【cheaper】 station                flag = -1;                for (i = Ncur + 1; i <= N&&node[i].d <= distance + Ccur*Davg; i++)                {                    if (node[i].p < Pcur)                    {                        flag = i;                        break;                    }                }                if (flag != -1)//find a station,and get there                {                    //price 未变                    Ccur -= (node[flag].d - distance) / Davg;//当前汽油数量===注意与下面表达式的计算顺序                    distance = node[flag].d;//当前距离                    Ncur = flag;//当前所在加油站                    Pcur = node[flag].p;//当前加油站的油价                    continue;                }                //else 1: 2.using 【Cmax】 find 【nearest】 【cheaper】 station                flag = -1;                for (i = Ncur + 1; i <= N&&node[i].d <= distance + Cmax*Davg; i++)                {                    if (node[i].p < Pcur)                    {                        flag = i;                        break;                    }                }                if (flag != -1)//find a station,and get there                {                    price += ((node[flag].d - distance) / Davg - Ccur)*node[Ncur].p;//当前花费                    distance = node[flag].d;//当前距离                    Ncur = flag;//当前所在加油站                    Pcur = node[flag].p;//当前加油站的油价                    Ccur = 0;//当前汽油数量：到K后的汽油为0                    continue;                }                //else 2: 3.get the Cmax and go as far as possible                flag = -1;                for (i = Ncur + 1; i <= N&&node[i].d <= distance + Cmax*Davg; i++)                {                    flag = i;                }                if (flag != -1)//can get some one station,and get there                {                    price += (Cmax - Ccur)*node[Ncur].p;//当前花费                    distance = node[flag].d;//当前距离                    Ncur = flag;//当前所在加油站                    Pcur = node[flag].p;//当前加油站的油价                    Ccur = Cmax - (node[flag].d - distance) / Davg;//当前汽油数量                    continue;                }                else//can not get some one station,over                {                    printf("The maximum travel distance = %.2f\n", distance + Cmax*Davg);                    break;                }            }            if (Ncur > N)            {                printf("%.2lf\n", price);            }        }    }    return 0;}