文档章节

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

 阿豪boy
发布于 2017/02/26 15:48
字数 1220
阅读 13
收藏 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;
}

 

© 著作权归作者所有

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

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

浣雨笑笑生
2015/09/13
1K
0
ip地址中的端口号

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

唧唧帝
2014/01/23
139
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
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
107
3
libdvbpsi源码分析(四)PAT表解析/重建

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

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

没有更多内容

加载失败,请刷新页面

加载更多

下一页

人生苦短:Python里的17个“超赞操作

人生苦短,我选Python”。那么,你真的掌握了Python吗? 1. 交换变量 有时候,当我们要交换两个变量的值时,一种常规的方法是创建一个临时变量,然后用它来进行交换。比如: # 输入 a = 5 b ...

糖宝lsh
38分钟前
4
0
咕泡-spring中常用设计模式概述

设计模式就是经验之谈,供后人借鉴,解决一些具有代表性的问题 设计模式来源于生活,反过来帮助我们更好生活 设计模式提升代码的可读性、可扩展性、维护成本、复杂业务问题 千万不要死记硬背...

职业搬砖20年
今天
2
0
day59-20180817-流利阅读笔记-待学习

假·照骗,真·社交焦虑 雪梨 2018-08-17 1.今日导读 发朋友圈之前,不少人为了展现更美好的生活状态会对照片加以“微调”,或是加个滤镜显得逼格更高,或是磨个皮瘦个脸拉个大长腿。现在,国...

aibinxiao
今天
18
0
OSChina 周五乱弹 —— 姑娘在这个节日里表白你接受么?

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @Sharon啊:完全被这个小姐姐圈粉了,学两首她的歌去哈哈 分享王贰浪的单曲《往后余生(翻自 马良)》 《往后余生(翻自 马良)》- 王贰浪 手...

小小编辑
今天
846
16
为什么HashMap要自己实现writeObject和readObject方法?

为什么HashMap要自己实现writeObject和readObject方法? 如果你有仔细阅读过HashMap的源码,那么你一定注意过一个问题:HashMap中有两个私有方法。 private void writeObject(java.io.Objec...

DemonsI
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部