//贪心算法解决加油站选择问题
//# 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[];
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 = ; 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 + , node + + N, cmp); if (N == || node[].d > 0.00001 || node[].d < -0.00001)//第一个站点不在距离0处
{
printf("The maximum travel distance = 0.00\n");
}
else//greedy now
{
price = ;//当前花费
distance = ;//当前距离
Ncur = ;//当前所在加油站
Ccur = ;//当前汽油数量
Pcur = node[].p;//当前加油站的油价
while (Ncur <= N)
{
//1.using 【remain】 gas find 【nearest】 【cheaper】 station
flag = -;
for (i = Ncur + ; i <= N&&node[i].d <= distance + Ccur*Davg; i++)
{
if (node[i].p < Pcur)
{
flag = i;
break;
}
}
if (flag != -)//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 = -;
for (i = Ncur + ; i <= N&&node[i].d <= distance + Cmax*Davg; i++)
{
if (node[i].p < Pcur)
{
flag = i;
break;
}
}
if (flag != -)//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 = ;//当前汽油数量:到K后的汽油为0
continue;
}
//else 2: 3.get the Cmax and go as far as possible
flag = -;
for (i = Ncur + ; i <= N&&node[i].d <= distance + Cmax*Davg; i++)
{
flag = i;
}
if (flag != -)//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 ;
}