文档章节

PAT A1033. To Fill or Not to Fill (25)

 阿豪boy
发布于 2017/02/26 15:48
字数 1220
阅读 12
收藏 0
点赞 0
评论 0

https://www.patest.cn/contests/pat-a-practise/1033

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.

Input Specification:

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.

Output Specification:

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.

Sample Input 1:

50 1300 12 8
6.00 1250
7.00 600
7.00 150
7.10 0
7.20 200
7.50 400
7.30 1000
6.85 300

Sample Output 1:

749.17

Sample Input 2:

50 1300 12 2
7.10 0
7.00 600

Sample Output 2:

The maximum travel distance = 1200.00

 

 

思路:

    起点与终点的距离为d,油箱最大油量为cmax,单位汽油能够支持前进davg

    1,把终点看作单位油价为0, 离起点距离为d的加油站,然后将所有加油站按照离起点的距离从小到大进行排序,排完序后,如果离离起点最近的加油站的距离不是0,则表示汽车无法出发(初始时刻油量为0),如果离起点最近的加油站距离是0,则进入2

    2,假设当前所处的加油站编号为now,接下来将从满油状态下能到达的所有加油站中选出下一个前往的加油站,策略如下

    (1),寻找距离当前加油站最近的油价低于当前油价的加油站记为k,加恰好能够到达加油站k的油,然后前往加油站k,即优先前往更低油价的加油站

    (2),如果找不到油价低于当前油价的加油站,则寻找油价最低的加油站,在当前加油站加满油,然后前往加油站k,即在没有更低油价的加油站时,前往油价尽可能低的加油站

    (3),如果在满油状态下都找不到能到达的加油站,则最远能到达的距离为当前加油站的距离加上满油状态下能前进的距离,结束算法,即没有加油站可以到达时结束算法

    

#include <iostream>
#include <cstdio>
#include <algorithm> 
using namespace std;

const int MAX = 510;
const int INF = 10000000;
struct Station {
	double price, dis;	//价格和距离 
}st[MAX];

//由小到大排序 
int cmp(Station a, Station b) {
	return a.dis < b.dis;
}

int main(int argc, char *argv[]) {
	int n;
	double cmax, d, davg;
	scanf("%lf%lf%lf%d", &cmax, &d, &davg, &n);

	for (int i = 0; i < n; i++)
		scanf("%lf%lf", &st[i].price, &st[i].dis);
	st[n].price = 0;		//终点是最后一站,价格为0,距离为d 
	st[n].dis = d;
	sort(st, st + n, cmp);	//按照距离将所有加油站从小到大排序
	if (st[0].dis != 0) {
		printf("The maximum travel distance = 0.00\n");
		return 0;
	}
	int now = 0;	//当前所处的加油站的编号
					//总花费,当前油量以及满油行驶距离
	double ans = 0, nowTank = 0, MAX = cmax*davg;
	while (now < n) {	//每次循环将选出下一个需要到达的加油站 
					//选出从当前加油站满油能到达范围内的第一个油价低于当前油价的加油站
					//如果没有油价低于当前加油站的,选择价格最低的那个
		int k = -1;		//最低油价的加油站编号
		double priceMin = INF;		//最低油价
		for (int i = now + 1; i <= n && st[i].dis - st[now].dis <= MAX; i++) {
			if (st[i].price < priceMin) {
				priceMin = st[i].price;
				k = i;
				//如果找到第一个油价低于当前油价的加油站,直接中断循环
				if (priceMin < st[now].price)
					break;
			}
		}

		if (k == -1) break; //满油状态下无法找到加油站,退出循环输出结果
							//下面为能找到可到达的加油站k计算转移花费
							//need是需要的油量
		double need = (st[k].dis - st[now].dis) / davg;
		if (priceMin < st[now].price) {//如果加油站k的油价低于当前油价 
									 //只卖足够到达k的油
			if (nowTank < need) {		//如果油量不足need 
				ans += (need - nowTank)*st[now].price; //补足need 
				nowTank = 0; 	//到达加油站k后油箱内油量为0 
			} else { //当前油量超过need 
				nowTank -= need; //直接到达加油站k 
			}
		} else {	//如果加油站k的油价高于当前油价 
			ans += (cmax - nowTank)*st[now].price; //油箱加满
												   //到达加油站k后油箱内油量为cmax-need
			nowTank = cmax - need;
		}
		now = k;	//到达加油站k,进入下一层循环	
	}
	//能到达终点 
	if (now == n) {
		printf("%.2f\n", ans);
	} else {
		printf("The maximum travel distance = %.2lf\n", st[now].dis + MAX);
	}

	return 0;
}

 

© 著作权归作者所有

共有 人打赏支持
粉丝 21
博文 881
码字总数 631558
作品 0
西安
Java正则表达式问号冒号的使用

  在Java和Javascript中正则表达式字符串前面加上?:表示非捕获型匹配,否则就是捕获型匹配。   捕获型括号会将匹配到的内容捕获到一些变量里,这些变量按照捕获型括号的左括号为顺序从1...

浣雨笑笑生 ⋅ 2015/09/13 ⋅ 0

ip地址中的端口号

概念 在网络技术中,端口(Port)大致有两种意思:、 一是物理意义上的端口,比如, Modem、集线器、交换机、路由器用于连接其他网络设备的接口; 二是逻辑意义上的端口,一般是指TCP/IP协议...

唧唧帝 ⋅ 2014/01/23 ⋅ 0

【PAT】1025. PAT Ranking (25)

题目 链接:https://www.patest.cn/contests/pat-a-practise/1025 Programming Ability Test (PAT) is organized by the College of Computer Science and Technology of Zhejiang Universi......

fanfan4569 ⋅ 02/01 ⋅ 0

libdvbpsi源码分析(四)PAT表解析/重建

由上一章libdvbpsi源码分析(三)PSI decocder详细分析,我们知道了psi decoder的构建过程。本章将延续上文 以PAT表详细解析为例,由点及面的概述libdvbpsi的实现。 下面详细分析pat decoder解...

地狱的烈火 ⋅ 2013/11/13 ⋅ 0

mysql查询语句

我要查询多张关联表的信息不知道哪里有错,下面是代码:select b.,pat.,per.,pese.,gro.* from bedtable b left join patient pat on b.pat_id = pat.id left join personalinformation per ......

温柔的美男子 ⋅ 2017/08/28 ⋅ 3

grep、sed、awk、perl等对正则表达式的支持的差别

在各种常用的工具中, 正则表达式如此的相似却又不同。 下表列出了一些常用的正则表达式,以及其不同之处。 项目总多,遗漏必有不少,请各位看官不吝指出。 以perl的正则为基准,不同的用法以...

流浪的洋葱 ⋅ 2014/11/20 ⋅ 0

go语言资料集合​

go语言资料集合 Go语言核心技术(卷一)之2.1-整数 Mac系统搭建Go语言Sublime Text 2环境配置 go语言实现排序算法 Go语言核心技术(卷一)之1.5-作用域 Go语言核心技术(卷一)之1.4-包和文件 ...

d_watson ⋅ 2016/03/16 ⋅ 0

理解PGA(2)pga_aggregate_target详解

注: 1)pgaaggregatetarget以下简称PAT 2)我的环境: 11:42:10 sys@ORCL (^ω^) select * from v$version where rownum=1; BANNER -----------------------------------------------------......

长平狐 ⋅ 2012/09/19 ⋅ 0

libdvbpsi源码分析(三)PSI decocder详细分析

由上一篇libdvbpsi源码分析(二)main函数,简单分析了demo程序中main函数的执行流程。现在将对具体的PSI表作详细解析。主要是对main函数中的libdvbpsiinit和dvbpsinew以及相关的dvbpsipat_att...

地狱的烈火 ⋅ 2013/11/12 ⋅ 0

JNI类型转换

声明: 本文由( 上善若水 )原创编译,转载请保留链接: JNI类型转换

LiSteven ⋅ 2013/08/02 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Python爬虫,抓取淘宝商品评论内容

作为一个资深吃货,网购各种零食是很频繁的,但是能否在浩瀚的商品库中找到合适的东西,就只能参考评论了!今天给大家分享用python做个抓取淘宝商品评论的小爬虫! 思路 我们就拿“德州扒鸡”...

python玩家 ⋅ 19分钟前 ⋅ 0

MySQL 内核深度优化

MYSQL数据库适用场景广泛,相较于Oracle、DB2性价比更高,Web网站、日志系统、数据仓库等场景都有MYSQL用武之地,但是也存在对于事务性支持不太好(MySQL 5.5版本开始默认引擎才是InnoDB事务...

java高级架构牛人 ⋅ 41分钟前 ⋅ 0

用户登录信息-钉子效果(基于jquery2.0)

本js效果使用jquery2.0,清晰的分解用户登录信息的(钉子效果),该效果直接用在作者网站(www.phpkhbd.com)上。 里面的难点有:定时器,延时。 大致效果如下: 一开始: 鼠标放上去的时候:...

宁哥实战课堂 ⋅ 43分钟前 ⋅ 0

解决yum安装报错Protected multilib versions

使用yum安装报错Protected multilib versions原因是因为多个库不能共存,不过更新的话也并不行,但是可以在安装命令后面加上如下一段命令: --setopt=protected_multilib=false 案例: 比如需...

北岩 ⋅ 54分钟前 ⋅ 0

为什么要学习Typescript???

简单来说 目前的typescript就是未来的javascript 为什么?? 这要从ECMA-262标准的第4版说起 对了 我们说的ES5 其实是ECMAScript3.1这个替代性建议被扶正了而已... 那么 第4版标准是什么? 看看...

hang1989 ⋅ 58分钟前 ⋅ 0

linux安装ipfs

一、下载ipfs # cd /usr/local/ipfs/ # wget https://dist.ipfs.io/go-ipfs/v0.4.15/go-ipfs_v0.4.15_linux-amd64.tar.gz # tar -zxvf go-ipfs_v0.4.15_linux-amd64.tar.gz 二、安装ipfs # ......

八戒八戒八戒 ⋅ 今天 ⋅ 0

jvm程序执行慢诊断手册

生产环境最多的几种事故之一就是程序执行慢,如果是web服务的话,表现就是响应时间长。本文分享,从业多年形成的排查守则。 诊断步骤 系统资源查看 首先是系统资源查看,而且必须是在第一步。...

xpbob ⋅ 今天 ⋅ 0

YII2 advanced 高级版本项目搭建-添加API应用以及多应用

一、YII安裝 安裝yii可以用composer安裝,也可以在yii中文社区下载归档文件安装 composer安装就不介绍了,因为要安装composer,比较麻烦,当然安装了composer是最好的,以后安装yii的插件要用...

botkenni ⋅ 今天 ⋅ 0

在jdk1.8的环境下模拟永久代内存溢出

相信不少小伙伴在看深入理解Java虚拟机的时候,作者给我们举例一个demo来发生PermGen space 1、通过List不断添加String.intern(); 2、通过设置对应的-XX:PermSize与-XX:MaxPermSize(更快看到...

虾几把写 ⋅ 今天 ⋅ 0

开发OpenDaylight组件的完整流程

在前面介绍学习了OpenDaylight的几个重要模块后,这里再来介绍下完整开发一个模块的过程。 OSGI的bundles提供被其他OSGI组件调用的服务。这个教程中展示的是Data Packet Service去解析数据包...

wangxuwei ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部