PAT刷题记录 1033 To Fill or Not to Fill
很有意思的一道贪心
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
double cmax, davg, dall;
int n;
struct Node
{
double price;
double dis;
}sta[505];
bool cmp1(Node a, Node b)
{
return a.dis < b.dis;
}
int main()
{
scanf("%lf%lf%lf%d", &cmax, &dall, &davg, &n);
for (int i = 0; i < n; ++i)
{
scanf("%lf%lf", &sta[i].price, &sta[i].dis);
}
sort(sta, sta + n, cmp1);
bool flag = false;
double far = 0;
int ns = 0;
int i1 = 0;
double min1 = 9999999;
double cost = 0;
double cnow = 0;
double bestprice;
while (sta[i1].dis == 0)
{
if (sta[i1].price < min1)
{
min1 = sta[i1].price;
ns = i1;
far = cmax * davg;
bestprice = sta[i1].price;
}
i1++;
}
if (min1 == 9999999)
{
printf("The maximum travel distance = 0.00");
return 0;
}
while (ns < n)
{
int i;
int u = -1;
double min = 9999999;
for (i = ns + 1; sta[i].dis <= far && i < n; ++i)
{
if (sta[i].price < min)
{
min = sta[i].price;
u = i;
if (min < sta[ns].price) //这一步超级重要!!!第一个比当前小的,就可以停了!后面有更小的,用现在贵的油跑更多也是浪费!
break;
}
}
if (u >= 0 && min < sta[ns].price) //如果下一个比当前便宜,只用加到够跑到下一站的油就够了
{
if (cnow < ((sta[u].dis - sta[ns].dis) / davg)) //因为之前会存在多加油的情况,要判断在那个基础上再加油,解释一下:cnow是当前油量(这里是在更新)
{
cost += ((sta[u].dis - sta[ns].dis) / davg - cnow) * sta[ns].price;
cnow = 0;
}
else
{
cnow -= (sta[u].dis - sta[ns].dis) / davg;
}
far = sta[u].dis + cmax * davg;
ns = u;
}
else if (u >= 0 && min >= sta[ns].price) //如果下一个反而贵,在当前就加满!
{
if (far >= dall) //事实证明这一步也很重要,结束的条件并不一定都是u==-1(也就是找不到下一个了),现在就能去终点,且下一站的油费比现在贵,现在就应该停
{
if (cnow < ((dall - sta[ns].dis) / davg))
{
cost += ((dall - sta[ns].dis) / davg - cnow) * sta[ns].price;
}
printf("%.2f", cost);
break;
}
cost += (cmax - cnow) * sta[ns].price;
cnow = cmax - (sta[u].dis - sta[ns].dis) / davg;
far = sta[u].dis + cmax * davg;
ns = u;
}
else if (u == -1 && far >= dall)
{
if (cnow < ((dall - sta[ns].dis) / davg))
{
cost += ((dall - sta[ns].dis) / davg - cnow) * sta[ns].price;
}
printf("%.2f", cost);
break;
}
else if (u == -1 && far < dall)
{
printf("The maximum travel distance = %.2f", far);
break;
}
}
return 0;
}
下一个加油站的选择,不是可到达范围里油费最便宜的,而是第一个比当前加油站油费便宜的!这一步自己刚开始一直是错的orz,典型的想当然
如果不能找到更便宜的下一站,这一站要加满。
还有一个点是判断结束的条件,现在可到达终点且之后的都贵,就可以停了。
最后修改于 2020-04-19