1033 To Fill or Not to Fill (25 分)

时间:2022-09-04 18:06:13
1033 To Fill or Not to Fill (25 分)

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: C​max​​ (≤ 100), the maximum capacity of the tank; D (≤30000), the distance between Hangzhou and the destination city; D​avg​​ (≤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: P​i​​, the unit gas price, and D​i​​ (≤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

分析:贪心,开始没做出来,后面参考晴神宝典。

假设当前加油站编号为now,每次从当前点开始搜索最大距离范围内的下一个要前往的加油站。

分3种情况:1、找到范围内第一个比当前加油站价格低的加油站k,加恰好能到达k的油,前往k。2、如果找不到比当前加油站价格低的加油站,则找范围内最小价格的加油站k,在当前加油站加满油,前往k。3、如果在满油状态下都找不到能到达的加油站,则最远能到达的距离为当前加油站的距离加上满油状态下能前进的距离,结束算法

 /**
 * Copyright(c)
 * All rights reserved.
 * Author : Mered1th
 * Date : 2019-02-25-22.01.39
 * Description : A1033
 */
 #include<cstdio>
 #include<cstring>
 #include<iostream>
 #include<cmath>
 #include<algorithm>
 #include<string>
 #include<unordered_set>
 #include<map>
 #include<vector>
 #include<set>
 using namespace std;
 ;
 ;
 struct Node{
     double price;
     double d;
 }node[maxn];
 bool cmp(Node a,Node b){
     return a.d<b.d;
 }
 int main(){
 #ifdef ONLINE_JUDGE
 #else
     freopen("1.txt", "r", stdin);
 #endif
     int n;
     double cmax,d,avg;
     cin>>cmax>>d>>avg>>n;
     ;i<n;i++){
         scanf("%lf %lf",&node[i].price,&node[i].d);
     }
     node[n].price=;
     node[n].d=d;  //终点
     sort(node,node+n,cmp);
     ].d!=){
         printf("The maximum travel distance = 0.00\n");
         ;
     }
     ; //当前加油站编号
     ,nowTank=,MAX=cmax*avg;//总花费、当前油量、最大行驶距离
     while(now < n){
         ; //最低油价的加油站编号
         double priceMin=INF;
         ;i<=n&&node[i].d-node[now].d<=MAX;i++){ //在最大行驶距离之内找到油价最低的站
             if(node[i].price<priceMin){
                 priceMin=node[i].price;
                 k=i;
                 //如果找到第一个油价低于当前油价的加油站,直接去那个加油站加油(跳出循环)
                 if(priceMin<node[now].price){
                     break;
                 }
             }
         }
         ) break; //没找到,跳出循环输出最大行驶距离
         double need=(node[k].d-node[now].d)/avg;
         if(priceMin<node[now].price){
             if(nowTank<need){
                 totalPrice+=(need-nowTank)*node[now].price;
                 nowTank=;
             }
             else{
                 nowTank-=need;
             }
         }
         else{
             totalPrice+=(cmax-nowTank)*node[now].price;
             nowTank=cmax-need;
         }
         now=k;
     }
     if(now==n){
         printf("%.2f\n",totalPrice);
     }
     else{
         printf("The maximum travel distance = %.2f\n",node[now].d+MAX);
     }
     ;
 }


1033 To Fill or Not to Fill (25 分)的更多相关文章

  1. 1033&period; To Fill or Not to Fill &lpar;25&rpar;

     题目链接:http://www.patest.cn/contests/pat-a-practise/1033 题目: 1033. To Fill or Not to Fill (25) 时间限制 1 ...

  2. 【贪心】PAT 1033&period; To Fill or Not to Fill &lpar;25&rpar;

    1033. To Fill or Not to Fill (25) 时间限制 10 ms 内存限制 32000 kB 代码长度限制 16000 B 判题程序 Standard 作者 ZHANG, Gu ...

  3. PAT 甲级 1033 To Fill or Not to Fill &lpar;25 分&rpar;(贪心&comma;误以为动态规划&comma;忽视了油量问题)&ast;

    1033 To Fill or Not to Fill (25 分)   With highways available, driving a car from Hangzhou to any oth ...

  4. PAT 1033 To Fill or Not to Fill&lbrack;dp&rsqb;

    1033 To Fill or Not to Fill(25 分) With highways available, driving a car from Hangzhou to any other ...

  5. pat1033&period; To Fill or Not to Fill &lpar;25&rpar;

    1033. To Fill or Not to Fill (25) 时间限制 10 ms 内存限制 65536 kB 代码长度限制 16000 B 判题程序 Standard 作者 ZHANG, Gu ...

  6. 1033 To Fill or Not to Fill

    PAT A 1033 To Fill or Not to Fill With highways available, driving a car from Hangzhou to any other ...

  7. PAT甲级1033&period; To Fill or Not to Fill

    PAT甲级1033. To Fill or Not to Fill 题意: 有了高速公路,从杭州到任何其他城市开车很容易.但由于一辆汽车的坦克容量有限,我们不得不在不时地找到加油站.不同的加油站可能会 ...

  8. PAT甲级——1033 To Fill or Not to Fill

    1033 To Fill or Not to Fill With highways available, driving a car from Hangzhou to any other city i ...

  9. PAT&lowbar;A1033&num;To Fill or Not to Fill

    Source: PAT A1033 To Fill or Not to Fill (25 分) Description: With highways available, driving a car ...

随机推荐

  1. C语言常见类型占用字节数

    前言 最近笔试经常遇到c语言各类型变量所占字节数的问题,这里做一个总结好了. 类型 常见的有char.int.long.short.float.double及指针等. 字符类型 这里单只char,ch ...

  2. easyui datagrid 点击表头的事件

    在用datagrid的时候我们可能要用到点击表头来触发一个function,这里有个简单的例子. 首先你得有个能用的datagrid. <div>    <table id=&quo ...

  3. 谈谈yii2-gii如何自定义模板

    作者:白狼 出处:http://www.manks.top/article/yii2_gii_custom_template本文版权归作者,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位 ...

  4. UEditor上传图片到七牛云储存(c&num;)

    我们的网站一般放在虚拟空间或者服务器上,图片如果存在本地目录,会占用很多空间和流量,还增加了负担,好的办法是把图片存放到云储存服务里面,平时用url去拿 云储存:普遍说又拍云和七牛比较好,看到七牛免费 ...

  5. Android开发之搜Ya项目说明(3)

    项目 搜芽移动client ----seller,app,base三个包的简单说明 作者 曾金龙 Tel:18664312687 QQ :470910357@qq.com 时间 2014-10-14 ...

  6. 决策树-C4&period;5算法(三)

    在上述两篇的文章中主要讲述了决策树的基础,但是在实际的应用中经常用到C4.5算法,C4.5算法是以ID3算法为基础,他在ID3算法上做了如下的改进: 1) 用信息增益率来选择属性,克服了用信息增益选择 ...

  7. Scrapy爬虫框架第一讲&lpar;Linux环境&rpar;

    1.What is Scrapy? 答:Scrapy是一个使用python语言(基于Twistec框架)编写的开源网络爬虫框架,其结构清晰.模块之间的耦合程度低,具有较强的扩张性,能满足各种需求.(前 ...

  8. 【Go】优雅的读取http请求或响应的数据-续

    原文链接:https://blog.thinkeridea.com/201902/go/you_ya_de_du_qu_http_qing_qiu_huo_xiang_ying_de_shu_ju_2 ...

  9. Learn Python3 the hard way 第二天总结 命令行&lpar;2&rpar;

    复制文件 命令:cp含义:很简单,就是把一个文件复制成一个新文件而已.使用 cp -r命令可以复制一些包含文件的目录 移动文件 命令:mv含义:对文件进行"rename". 查看文 ...

  10. selenium&plus;python自动化98--文件下载弹窗处理&lpar;PyKeyboard&rpar;

    前言 在web自动化下载操作时,有时候会弹出下载框,这种下载框不属于web的页面,是没办法去定位的(有些同学一说到点击,脑袋里面就是定位!定位!定位!) 有时候我们并不是非要去定位到这个按钮再去点击, ...