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