贪心算法解决To Fill or Not to Fill

这篇具有很好参考价值的文章主要介绍了贪心算法解决To Fill or Not to Fill。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目概述

With highways available, driving a car from Hangzhou to any other city is easy. But since the tank capacity of a car is limited, we have to find gas stations on the way from time to time. Different gas station may give different price. You are asked to carefully design the cheapest route to go.
Each input file contains one test case. For each case, the first line contains 4 positive numbers: Cmax (<= 100), the maximum capacity of the tank; D (<=30000), the distance between Hangzhou and the destination city; Davg (<=20), the average distance per unit gas that the car can run; and N (<= 500), the total number of gas stations. Then N lines follow, each contains a pair of non-negative numbers: Pi, the unit gas price, and Di (<=D), the distance between this station and Hangzhou, for i=1,…N. All the numbers in a line are separated by a space.
For each test case, print the cheapest price in a line, accurate up to 2 decimal places. It is assumed that the tank is empty at the beginning. If it is impossible to reach the destination, print “The maximum travel distance = X” where X is the maximum possible distance the car can run, accurate up to 2 decimal places.
题目大意:
现需要从杭州出发沿高速公路前往某目的地,已知车油箱最大容量、总距离、每单位车油走的距离和沿途的加油站总数,并给出每个加油站的单位油价和离杭州(出发地)的距离,让你计算出到达目的地可能的最小花费,若不可能到达,需要给出能够到达的最大距离。输出要求具体见题干(原题即为英文题)。

算法分析

本题本质上是特定情境下的价格最优化的问题,本来车的油箱是空的,所以车这一路上的车油必须从沿途的加油站获得,当然即便原来有油我们也可以通过改变最大容量转化为等价的问题,我们需要找出使得花费最小的策略。考虑这样的一般情形:我们到达了某一个加油站,但这时无法不经过别的加油站直接到达终点,且加满油可覆盖的最大里程内有若干加油站,此时如何从中选择下面将要前往的加油站?有下面两种可能性:
1.在这些加油站中没有比当前加油站的油价更低的,需要清楚的是我们必须在这些最大车程能覆盖到的加油站里选择一个前往加油,否则是不够支持我们到达目的地的,那么,当然要选择这其中价格最便宜的。因此针对这种情况,我们应当在当前的加油站把油加满,然后前往上述价格最便宜的加油站;
2.在这些加油站中存在比当前加油站的油价更低的,假设这样的加油站存在多个,我们应当选择距离最近的一个前往,因为我们不必把油加满,而是加到刚好够到达下一个加油站就可以了,毕竟更便宜嘛,当然如果不加油足够到达的话在当前加油站就不用做任何操作,这样一来优先选择最近的价格更低的加油站在同样的车途中总可以使开销得到降低,读者可以停下来仔细思考一下其中的道理。
以上就介绍完了贪心思想的主体部分,为了完整地解决问题我们还需要考虑如下几个特殊情形:
1.起点没有加油站,这样车走不了一点,返回最大距离0.00;
2.两个加油站距离太远,即便在当前加油站把油加满也到达不了,返回最大距离:当前行驶距离+油加满能行驶的最大距离;
3.终点如何处理?可以看到我们算法的主体部分都在讨论加油站的事情,这时候就需要我们开创性地把终点理解为一个油价为0的车站,其离出发地的距离就是总距离。
此外,为了提高算法效率,我们需要先按距离远近由近到远排序各加油站(包括终点,但您会发现由于终点的特性,它永远会被排在最后一个),难免会遇到两个加油站距离相等的情况,这时候要按油价从低到高排序(这样会避免某些无效操作)。

代码实现

经过一个下午的鏖战,代码总算是写出来了,读者可以先根据上面的分析自己尝试编写,再参考在下的拙迹:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
struct station{
	double price;
	double dis;
};
vector<station> sta;
bool cmp(station a,station b){
	if(a.dis==b.dis) return a.price<b.price;
	else return a.dis<b.dis;
}
int main(){
	double cMax,dTotal,dPergas;
	int n;
	while(scanf("%lf%lf%lf%d",&cMax,&dTotal,&dPergas,&n)!=EOF){
		sta.clear();
		station temp = {0.0,dTotal};
		//printf("%.2f %.2f\n",temp.price,temp.dis);
		sta.push_back(temp);
		for(int i=1;i<=n;i++){
			scanf("%lf%lf",&(temp.price),&(temp.dis));
			sta.push_back(temp);
		}
		//sort可保证终点排在最后 
		sort(sta.begin(),sta.end(),cmp);
		double nowDis=0.0,nowPrice=0.0,fuel=0.0;
		double maxRun = cMax*dPergas;
		int cheapest,nearest;
		for(int i=0;i<n;i++){
			//一开始忘记这步处理,但是多点测试通过了,纯属运气好 
			if(sta[i]!=nowDis)printf("The maximum travel distance = %.2f\n",nowDis);
			if((sta[i+1].dis-sta[i].dis)>maxRun){
				printf("The maximum travel distance = %.2f\n",nowDis+maxRun);
				break;
			}
			cheapest = nearest = i+1;
			int flag = 0;
			for(int j=i+1;j<=n&&(sta[j].dis-sta[i].dis)<=maxRun;j++){
				if(sta[j].price<sta[i].price){
					nearest = j;
					flag = 1;
					break;
				}
			}
			if(flag==0){//合法距离的加油站中,没有比当前价格更便宜的
				//找到最便宜的加油站 
				for(int j=i+1;j<=n&&(sta[j].dis-sta[i].dis)<=maxRun;j++){
					if(sta[cheapest].price>sta[j].price){
						cheapest = j;
					}
				}
				//把油加满,去往
				nowPrice += (cMax - fuel) * sta[i].price;
				fuel = cMax - (sta[cheapest].dis - sta[i].dis)/dPergas;
				nowDis = sta[cheapest].dis;
				i = cheapest - 1;
			}else{
				//找到了更便宜的加油站
				//最最便宜的加油站便是终点 
				double fuelReq = (sta[nearest].dis-sta[i].dis)/dPergas;
				if(fuelReq>fuel){
					nowPrice += (fuelReq - fuel) * sta[i].price;
					fuel = fuelReq;
				}
				fuel -= fuelReq;
				nowDis = sta[nearest].dis;
				i = nearest - 1;
			}
			//printf("flag:%d,nowPrice:%.2f,nowDis:%.2f,i:%d\n",flag,nowPrice,nowDis,i);
		}
		if(nowDis==dTotal)printf("%.2f\n",nowPrice);
	}
	return 0;
}

问题与总结

贪心算法是一类比较灵活的算法,记得之前上算法课的时候,老师讲过两个比较经典的题型:背包问题和驳船装货问题。但最近笔者在准备PAT考试的刷题过程中,发现可以用贪心算法解决的问题远不局限于此,也练到了不少好题,但这道让我受的磨折最为深刻,所以决定写这篇博客记录一下解题历程。
说到问题,这次可大有可说,to be honest,第一次写成的时候,我的算法思路是清晰正确的,但是运行时还是各种错,按照时间顺序,我遇到的问题见下:
1.无论输入数据是什么都输出The maximum travel distance = 0.00。要知道你检查了数遍算法发现逻辑没有一丁点毛病,但结果每回都是令人绝望的0.00。其原因后来灵光一现发现自己在接受双精度浮点型输入的时候没有使用**lf!!**咱就是说,还整啥scanf啊?C++的cin不香吗T^T
2.测试数据输出的结果是81,正确答案为82.89,再次说明本人的算法是没有毛病的,但是这代码要想跑通还真是命途多舛,我当时刚解决完上一个问题,明媚的心情立刻被这个bug弄得愁云密布,然后我出去散了会步,突然领会到,这个答案是整数相除产生的bug!然后我产生了一个令我自己都大跌眼镜的猜想:难道两个小数部分相同的浮点数相减,会自动变成一个整型数吗?

我立刻打开百度搜索,发现有人在php编程的时候会遇到类似的情况,在咖啡店喝完咖啡,我立刻飞奔回家想要看看是不是C编程真的存在这样惊世骇俗的Bug,然后我发现自己用int型变量接受了浮点数相减结果的事实,沉默不过3秒,我默默把int改回了double,输入测试数据得到正确答案82.89,而我由于被自己蠢到甚至没有任何情绪波动:P
3.虽然多点测试通过了,但之后复盘的时候发现自己原来的代码并不能解决起点没有加油站这种情况,经过思索后在while循环了里加上对于nowDis是否等于当前加油站距起点距离的判断,如果不存在这种特殊情况这一判断是显然成立的。文章来源地址https://www.toymoban.com/news/detail-834283.html

到了这里,关于贪心算法解决To Fill or Not to Fill的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Unable to connect to the server: x509: certificate has expired or is not yet valid

    手动更新所有证书,执行命令 更新用户配置 用更新后的admin.conf替换/root/.kube/config文件 k8s解决证书过期官方文档:https://kubernetes.io/zh-cn/docs/tasks/administer-cluster/kubeadm/kubeadm-certs/ 帮助文档: https://www.cnblogs.com/00986014w/p/13095628.html

    2024年02月04日
    浏览(59)
  • K8S异常之Unable to connect to the server: x509: certificate has expired or is not yet valid

    2.1 处理步骤 2.2 处理步骤详细情况 如上,发现很多证书都是 invalid 的状态,接着更新证书: 如下,更新证书后,证书过期时间已经更新为 365d 3.1 再次查看kubectl get node,发现有新的错误: error: You must be logged in to the server (Unauthorized) 3.2 上述错误解决方案 备份配置文件 cp -rp

    2024年02月03日
    浏览(68)
  • ERROR: Could not install packages due to an OSError: [Errno 2] No such file or directory:报错处理 ERROR: Could not install packages due to an OSError: [Errno 2] No such file or directory:报错处理

    需要特别注意的是,安装MNE时候需要注意环境,我的是激活tensorflow后安装在相应的文件夹之下的。而前面的括号(cat)是我给我的tensorflow命名的。不要在意这些细节了。哈哈。 安装MNE工具包出现报错: ERROR: Could not install packages due to an OSError: [Errno 2] No such file or directory: \\\'d

    2024年02月13日
    浏览(59)
  • ORA-20000: Unable to set values for index xxx: does not exist or insufficient privileges

    使用expdp/impdp导出导入数据时,遇到ORA-2000错误,如下所示: 导出环境为Oracle 12c,导入的数据库环境为Oracle 19c,具体版本为19.16.0.0.0,查了一下Oracle Support,刚好是遇到了Bug 30978304,关于为什么会出现这个错误, ORA-20000 from Data Pump Import (IMPDP) when PK Constraint does not Create a New In

    2024年02月12日
    浏览(68)
  • Jmeter 启动时报错:Not able to find Java executable or version. Please check your Java installation.

    在启动Jmeter的时候,突然报错 Not able to find Java executable or version. Please check your Java installation. 尽管本人安装了JDK。 经过小编的不懈努力,终于找到了解决方法。亲测有效!!! 只需要在 jmeter.bat文件 里面加上下面这两行即可(放在最前面就行): SET JAVA_HOME=C:Program FilesJav

    2024年02月12日
    浏览(42)
  • 【已解决】 Unable to attach or mount volumes: unmounted volumes

      安装nfs-provide-client的时候pod 一直不能启动,报错Unable to attach or mount volumes:  wrong fs type, wrong fs type, bad option ?? 先找了个客户端挂载,试了下,发现是可以写入到nfs-server的挂载路径的 但是安装的nfs-provider却启动不来 然后发现是要挂载NFS的客户端【就是node 节点】 没有安

    2024年02月12日
    浏览(47)
  • 【Tomcat】:One or more listeners failed to start.报错解决方案

    具体就是web.xml此配置报错: 服务器启动错误Tomcat:One or more listeners failed to start.报错解决方案 IDEA:在使用IDEA运行SSM项目的时候 , Tomcat运行失败 , 出现好几次 , 具体报错\\\"One or more listeners failed to start. Full details will be found in the appropriate container log file\\\" 具体有一下几种解决方案: 法

    2024年02月19日
    浏览(55)
  • failed to open stream: No such file or directory问题解决大全

    这篇文章主要为大家详细介绍了failed to open stream: No such file or directory问题解决大全,具有一定的参考价值,感兴趣的小伙伴们可以参考一下,有需要的朋友可以收藏方便以后借鉴。 failed to open stream: No such file or directory是PHP站点经常可能会遇到的问题,361源码做了个总结,希望

    2024年02月09日
    浏览(60)
  • 已解决1.Downgrade the protobuf package to 3.20.x or lower.

    已解决TypeError: Descriptors cannot not be created directly. If this call came from a _pb2.py file, your generated code is out of date and must be regenerated with protoc = 3.19.0. If you cannot immediately regenerate your protos, some other possible workarounds are: 1.Downgrade the protobuf package to 3.20.x or lower. 2.Set PROTOCOL_BUFFERS_PYTHON_IMPLEM

    2024年02月12日
    浏览(39)
  • 已解决1. Downgrade the protobuf package to 3.20.x or lower.

    已解决TypeError: Descriptors cannot not be created directly. If this call came from a _pb2.py file, your generated code is out of date and must be regenerated with protoc = 3.1.0If you cannot immediately regenerate your protos, some other possible workarounds are: 1. Downgrade the protobuf package to 3.20.x or lower. 2. Set PROTOCOL_BUPFERS_PYTHON_iMPLEME

    2023年04月17日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包