九度oj 1437 To Fill or Not to Fill 2012年浙江大学计算机及软件工程研究生机试真题

时间:2022-09-04 18:10:47

题目1437:To Fill or Not to Fill

时间限制:1 秒

内存限制:128 兆

特殊判题:

提交:1488

解决:345

题目描述:

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.

输入:

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.

样例输入:
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
50 1300 12 2
7.10 0
7.00 600
样例输出:
749.17
The maximum travel distance = 1200.00
来源:
2012年浙江大学计算机及软件工程研究生机试真题
分析:
 //贪心算法
//dis=满油箱可以开出的最远距离。
//算法描述:起点A开始,到A+dis范围内:
//1.如果存在点B的s[B].price<=s[A].price,只要满足能行驶到B点即可
//2.如果不存在点B的s[B].price<=s[A].price,则要使车能开到 A+dis范围内除A以外,price最小的点--min_index所指点
//注意:
//1.终点如果在 A+dis范围内,一定可达
//2.注意排序后第一个点的dis可能不为0
//3.离A点最近的B点与A的距离如果>dis,则此趟行驶到不了终点
//4.油箱的情况每次都要关注
//具体见代码:
#include<iostream>
#include<queue>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
struct station{
double price,dis;
};
station s[];
bool cmp(station a,station b){
return a.dis<b.dis;
}
int main(){
double cmax,d,davg;
int n;
while(scanf("%lf%lf%lf%d",&cmax,&d,&davg,&n)!=EOF){
double min_price=;
double max_dis=;
double cur_tank=;
int i=;
for(;i<n;i++){
cin>>s[i].price>>s[i].dis;
}
s[i].dis=d;
s[i].price=;
sort(s,s+n,cmp);
/*for(i=0;i<=n;i++){
cout<<s[i].dis<<' '<<s[i].price<<endl;
}*/
if(s[].dis>){//2.注意排序后第一个点的dis可能不为0
//cout<<1<<endl;
printf("The maximum travel distance = 0.00\n");
continue;
}
int f=;
double dis=cmax*davg;
int min_index;
while(s[f].dis<d){
int next=f+;
min_index=next;
while((s[next].dis-s[f].dis)<=dis){//如果next==n,一定会从break处出去
//跳出循环只有三种情况:
//1.在dis范围内,没有点与f点的距离小于等于dis
//2.在dis范围内,找到price小于f的点(包括next==n)
//3.next!=n,但在dis范围内,没有找到price小于f的点。在dis范围内,有点与f点的距离小于等于dis
if(s[next].price<s[min_index].price){//记录最小的油价的站点
min_index=next;
}
if(s[next].price<=s[f].price){//在dis范围内,找到price小于f的点
break;
}
next++;
}
if(next==f+&&(s[next].dis-s[f].dis)>dis){//1.在dis范围内,没有点与f点的距离小于等于dis
//cout<<1<<endl;
max_dis+=dis;
break;
}
else{
if((s[next].dis-s[f].dis)<=dis){//2.在dis范围内,找到price小于f的点(包括next==n)
if(s[next].dis-s[f].dis>cur_tank){
min_price+=(s[next].dis-s[f].dis-cur_tank)*s[f].price;
cur_tank=;
max_dis+=s[next].dis-s[f].dis;
}
else{
cur_tank-=s[next].dis-s[f].dis;
max_dis+=s[next].dis-s[f].dis;
}
f=next;
}
else{//3.next!=n,但在dis范围内,没有找到price小于f的点。在dis范围内,有点与f点的距离小于等于dis
min_price+=(dis-cur_tank)*s[f].price;
cur_tank=dis-(s[min_index].dis-s[f].dis);
max_dis+=s[min_index].dis-s[f].dis;
f=min_index;
}
}
}
if(s[f].dis==d){
printf("%.2lf\n",min_price/davg);
}
else{
printf("The maximum travel distance = %.2lf\n",max_dis*1.0);//注意输出格式
}
}
return ;
}
 

九度oj 1437 To Fill or Not to Fill 2012年浙江大学计算机及软件工程研究生机试真题的更多相关文章

  1. 九度oj 1468 Sharing 2012年浙江大学计算机及软件工程研究生机试真题

    题目1468:Sharing 时间限制:1 秒 内存限制:128 兆 特殊判题:否 提交:2687 解决:550 题目描述: To store English words, one method is ...

  2. 九度oj 1464 Hello World for U 2012年浙江大学计算机及软件工程研究生机试真题

    题目1464:Hello World for U 时间限制:1 秒 内存限制:128 兆 特殊判题:否 提交:3872 解决:1082 题目描述: Given any string of N (&gt ...

  3. 九度OJ 1019 简单计算器 -- 2006年浙江大学计算机及软件工程研究生机试真题

    题目地址:http://ac.jobdu.com/problem.php?pid=1019 题目描述:     读入一个只包含 +, -, *, / 的非负整数计算表达式,计算该表达式的值. 输入: ...

  4. 九度oj 1034 寻找大富翁 2009年浙江大学计算机及软件工程研究生机试真题

    题目1034:寻找大富翁 时间限制:1 秒 内存限制:32 兆 特殊判题:否 提交:5323 解决:2123 题目描述:     浙江桐乡乌镇共有n个人,请找出该镇上的前m个大富翁. 输入:     ...

  5. 九度oj 1031 xxx定律 2009年浙江大学计算机及软件工程研究生机试真题

    题目1031:xxx定律 时间限制:1 秒 内存限制:32 兆 特殊判题:否 提交:5153 解决:3298 题目描述:     对于一个数n,如果是偶数,就把n砍掉一半:如果是奇数,把n变成 3*n ...

  6. 九度oj 1032 ZOJ 2009年浙江大学计算机及软件工程研究生机试真题

    题目1032:ZOJ 时间限制:1 秒 内存限制:32 兆 特殊判题:否 提交:4102 解决:2277 题目描述: 读入一个字符串,字符串中包含ZOJ三个字符,个数不一定相等,按ZOJ的顺序输出,当 ...

  7. 九度oj 1006 ZOJ问题 2010年浙江大学计算机及软件工程研究生机试真题

    题目1006:ZOJ问题 时间限制:1 秒 内存限制:32 兆 特殊判题:否 提交:16244 解决:2742 题目描述: 对给定的字符串(只包含'z','o','j'三种字符),判断他是否能AC.是 ...

  8. 九度oj 1004 Median 2011年浙江大学计算机及软件工程研究生机试真题

    题目1004:Median 时间限制:1 秒 内存限制:32 兆 特殊判题:否 提交:14162 解决:3887 题目描述: Given an increasing sequence S of N i ...

  9. 九度oj 1003 A&plus;B 2010年浙江大学计算机及软件工程研究生机试真题

    题目1003:A+B 时间限制:1 秒 内存限制:32 兆 特殊判题:否 提交:12812 解决:5345 题目描述: 给定两个整数A和B,其表示形式是:从个位开始,每三位数用逗号",&qu ...

随机推荐

  1. redis主从

    安装: tar -zxvf redis-3.2.6.tar.gz cd redis-3.2.6make make installcd utils/ sh install_server.sh 主: 配置 ...

  2. Linux System Calls Hooking Method Summary

    http://www.cnblogs.com/LittleHann/p/3854977.html http://www.cnblogs.com/cozy/articles/3175615.html h ...

  3. AFNetWorking支持解析html的方法

    在AFURLResponseSeriallzation.m的226行 手动添加@"text/html" 添加之前解锁文件

  4. &lbrack;redis&rsqb; windwos下安装和使用redis

    一篇很好的入门学习文章:Redis学习 Redis是一种nosql数据库,在开发中常用做缓存. 1.下载地址: 低版本下载地址:https://github.com/dmajkic/redis/dow ...

  5. java网格布局管理器

    public class GirdLayoutPosition extends JFrame{    public GirdLayoutPosition()    {        Container ...

  6. scala实现Netty通信

    在学习spark源码的时候看到spark在1.6之后底层的通信框架变成了akka和netty两种方式,默认的是用netty根据源码的思路用scala写了一个Demo级别的netty通信 package ...

  7. &lbrack;Papers&rsqb;MHD&comma; &dollar;&bsol;p&lowbar;3&bsol;pi&dollar;&comma; Lebesgue space &lbrack;Cao-Wu&comma; JDE&comma; 2010&rsqb;

    $$\bex \p_3\pi\in L^p(0,T;L^q(\bbR^3)),\quad \frac{2}{p}+\frac{3}{q}=\frac{12}{7},\quad \frac{12}{7} ...

  8. 方法:怎么用ionic命令行调试你的ionic app

    官网上有很详细的解说  http://blog.ionic.io/live-reload-all-things-ionic-cli/ 下面说说我自己的调试过程(android版): 首先用命令行进入你 ...

  9. mysql权限设置

    想要设定权限,必须通过root用户登录: >> grant all privileges on *.* to root@"%" identified by " ...

  10. &lbrack;记录&rsqb;CentOS搭建SVN服务器&lpar;主从同步&rpar;

    CentOS搭建SVN服务器(主从同步)1.安装步骤如下: 1)安装: #yum install subversion 2)查看安装位置: #rpm -ql subversion 3)查看版本: #/ ...