10.10解题报告 旅行家的预算

旅行家的预算

题目描述
一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离D1、汽车油箱的容量C（以升为单位）、每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途油站数N（N可以为零），油站i离出发点的距离Di、每升汽油价格Pi（i=1,2,…,N）。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“No Solution”。

输入格式
第一行，D1，C，D2，P，N。
接下来有N行。
第i+1行，两个数字，油站i离出发点的距离Di和每升汽油价格Pi。
输出格式
所需最小费用，计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“No Solution”。

输入输出样例
输入 #1
275.6 11.9 27.4 2.8 2
102.0 2.9
220.0 2.2
输出 #1
26.95

其实这道题的思路还是挺简单的 就找能到的范围里 油钱最低的 然后把油加满。
典型的模拟加搜索 就是有点恶心 模拟题一般都不是很好写 笑
我一开始是直接按价格排序 然后wa了一个点 最后发现我第一次到的时候没有把油加满 但是因为我太（脑）累（抽）了（了）所以没改出来 还得仰望洛谷的大佬在讨论区帮帮孩子
因为价格排序的那个代码没改出来 我就去重（抄）构（题）代（解）码（了），写出了这个以路径排序的
然后就是核心代码了

void solve(int now,double left)//当前油站 剩余油量 
{
	int minn;//当前能到的价格最低的油站的标号 
	double value1=99999.9;//当前最低的价格 
	for(int i=now+1;i<=n;i++)
	{
		if(mapp[i].dis>mapp[now].dis+maxn)
		break;
		if(mapp[i].value<value1)//找到最低油站 
		{
			value1=mapp[i].value;
			minn=i;
		}
	}
	if(mapp[now].value<=value1&&mapp[now].dis+maxn>=d1)//要是我现在所在的油站价格的价钱是最低的并且能到达终点 一路走下去 
	{
		mon+=((d1-mapp[now].dis)/d2-left)*mapp[now].value;
		printf("%.2lf\n",mon);
		return ;
	}
	if(value1==99999.9)//到不了其他油站并且到不了终点 
	{
		printf("No Solution\n");
		return ;
	}
	if(mapp[now].value<value1)//到不了终点但当前油站是最低的 
	{
		mon+=(c-left)*mapp[now].value;//把油箱加满 在下一个没有那么便宜的油站少加点油 
		left=c-(mapp[minn].dis-mapp[now].dis)/d2;
	}
	else
	{
		mon+=((mapp[minn].dis-mapp[now].dis)/d2-left)*mapp[now].value;//不是最便宜的就不加满,狗到下一个油站就算成功 
		left=0.0;
	}
	solve(minn,left);

大概就是这样
附上完整的ac代码：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;

struct lwt
{
	double dis;
	double value;
}mapp[11];

bool cmp(lwt a,lwt b)
{
	return a.dis<b.dis;
}

void solve(int now,double left);

double d1,c,d2,p,maxn,mon;
int n;

int main()
{
	
	scanf("%lf%lf%lf%lf%d",&d1,&c,&d2,&p,&n);
	
	mapp[0].dis=0;
	mapp[0].value=p;
	maxn=c*d2;
	for(int i=1;i<=n;i++)
	scanf("%lf%lf",&mapp[i].dis,&mapp[i].value);
	
	sort(mapp+1,mapp+1+n,cmp);
	
	solve(0,0.0);
	
	return 0;
}

void solve(int now,double left)//当前油站 剩余油量 
{
	int minn;//当前能到的价格最低的油站的标号 
	double value1=99999.9;//当前最低的价格 
	for(int i=now+1;i<=n;i++)
	{
		if(mapp[i].dis>mapp[now].dis+maxn)
		break;
		if(mapp[i].value<value1)//找到最低油站 
		{
			value1=mapp[i].value;
			minn=i;
		}
	}
	if(mapp[now].value<=value1&&mapp[now].dis+maxn>=d1)//要是我现在所在的油站价格的价钱是最低的并且能到达终点 一路走下去 
	{
		mon+=((d1-mapp[now].dis)/d2-left)*mapp[now].value;
		printf("%.2lf\n",mon);
		return ;
	}
	if(value1==99999.9)//到不了其他油站并且到不了终点 
	{
		printf("No Solution\n");
		return ;
	}
	if(mapp[now].value<value1)//到不了终点但当前油站是最低的 
	{
		mon+=(c-left)*mapp[now].value;//把油箱加满 在下一个没有那么便宜的油站少加点油 
		left=c-(mapp[minn].dis-mapp[now].dis)/d2;
	}
	else
	{
		mon+=((mapp[minn].dis-mapp[now].dis)/d2-left)*mapp[now].value;//不是最便宜的就不加满,狗到下一个油站就算成功 
		left=0.0;
	}
	solve(minn,left);
}