首页 > 其他分享 >洛谷P1016

洛谷P1016

时间:2024-09-17 09:52:02浏览次数:3  
标签:不能到达 加满 洛谷 NN 每升 P1016 加油站 油箱

题目传送门:传送门p1016

题目描述

一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市(假设出发时油箱是空的)。给定两个城市之间的距离 D1D1​、汽车油箱的容量 CC(以升为单位)、每升汽油能行驶的距离 D2D2​、出发点每升汽油价格PP和沿途油站数 NN(NN 可以为零),油站 ii 离出发点的距离 DiDi​、每升汽油价格 PiPi​(i=1,2,…,Ni=1,2,…,N)。计算结果四舍五入至小数点后两位。如果无法到达目的地,则输出 No Solution

输入格式

第一行,D1D1​,CC,D2D2​,PP,NN。

接下来有 NN 行。

第 i+1i+1 行,两个数字,油站 ii 离出发点的距离 DiDi​ 和每升汽油价格 PiPi​。

输出格式

所需最小费用,计算结果四舍五入至小数点后两位。如果无法到达目的地,则输出 No Solution

输入输出样例

输入 #1

275.6 11.9 27.4 2.8 2
102.0 2.9
220.0 2.2

输出 #1

26.95

说明/提示

N≤6N≤6,其余数字 ≤500≤500。

NOIP1999 普及组第三题、提高组第三题

这道题目应该算是妥妥的贪心+模拟吧……

算法原理如下:

1.枚举途中经过的加油站,每经过一个加油站,计算一次花费;

2.在一个加油站所需要加的油,就是能够支持它到达下一个油价比它低的加油站的量;

3.如果在这个加油站即使加满油,都不能到达一个比它油价低的加油站,就把油箱加满,前往能够到达的加油站中油价最低的那个;

4.如果在这个加油站即使加满油,都不能到达任意一个加油站,也不能到达终点城市,说明无解;

**第三点:为什么要加满油?**因为这样可以减少在下一个加油站(价格更贵)所需要加的油量。

AC代码:

#include<bits/stdc++.h>
using namespace std;
double maxx,mo=0,d2,temlen=0,d1,c,p;
//temlen:油箱中在到达了下一个加油站时油箱中的剩余油量可以继续

标签:不能到达,加满,洛谷,NN,每升,P1016,加油站,油箱
From: https://blog.csdn.net/xiachake/article/details/142282606

相关文章

  • 洛谷P10973 Coins
    //经典多重背包动态规划题#include<iostream>#include<cstring>usingnamespacestd;constintN=1e5+10;intused[N];intf[N],a[N],c[N];intn,m;intmain(){  while(cin>>n>>m&&(n||m))  {    memset(f,0,sizeoff);f[0]......
  • 【洛谷 P1216】[USACO1.5] [IOI1994]数字三角形 Number Triangles 题解(动态规划)
    [USACO1.5][IOI1994]数字三角形NumberTriangles题目描述观察下面的数字金字塔。写一个程序来查找从最高点到底部任意处结束的路径,使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。在上面的样例中,从的路径产生了最大权值。输入格式第一个行一个正整数......
  • dfs与贪心算法——洛谷5194
    问题描述:有n个砝码,将砝码从大到小排列,从第三个砝码开始,所有砝码均大于其前两个砝码之和,问怎样的砝码组合才可以组合出不大于c的最大重量,输出该重量输入:第一行输入两个个整数N,c,代表有N个砝码,第二行输入N个砝码的质量输出:不大于c的最大重量题目分析:要找到不大于c的最大重量,要......
  • 打卡信奥刷题(761)用Scratch图形化工具信奥P5713[普及组/提高组] 【深基3.例5】洛谷团队
    【深基3.例5】洛谷团队系统题目描述在洛谷上使用团队系统非常方便的添加自己的题目。如果在自己的电脑上配置题目和测试数据,每题需要花费时间555分钟;而在洛谷团队中上......
  • 【洛谷 P1596】[USACO10OCT] Lake Counting S 题解(深度优先搜索)
    [USACO10OCT]LakeCountingS题面翻译由于近期的降雨,雨水汇集在农民约翰的田地不同的地方。我们用一个的网格图表示。每个网格中有水(W)或是旱地(.)。一个网格与其周围的八个网格相连,而一组相连的网格视为一个水坑。约翰想弄清楚他的田地已经形成了多少水坑。给出约翰田地的示意图,......
  • 洛谷题单指南-分治与倍增-P2415 集合求和
    原题链接:https://www.luogu.com.cn/problem/P2415题意解读:计算集合所有子集中元素之和。解题思路:集合的特性:互异性,元素各不相同来看样例:23,可以组成的子集有空23232和3都出现2次再比如:123,可以组成的子集有空12312 13231231,2,3各出现4次由于在集合中......
  • 洛谷P1004
    题目传送门:传送门p1004题目背景NOIP2000提高组T4题目描述设有 N×NN×N 的方格图 (N≤9)(N≤9),我们将其中的某些方格中填入正整数,而其他的方格中则放入数字 00。如下图所示(见样例):某人从图的左上角的 AA 点出发,可以向下行走,也可以向右走,直到到达右下角的 BB ......
  • 洛谷P1006
    题目传送门:传送门p1006题目描述小渊和小轩是好朋友也是同班同学,他们在一起总有谈不完的话题。一次素质拓展活动中,班上同学安排坐成一个 mm 行 nn 列的矩阵,而小渊和小轩被安排在矩阵对角线的两端,因此,他们就无法直接交谈了。幸运的是,他们可以通过传纸条来进行交流。纸条要......
  • 【LGR-200-Div.4】洛谷入门赛 #27 A-H题解
    A#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;mt19937rnd(time(0));#defineintlonglongtypedeftuple<int,int,int>tp;#definexfirst#defineysecondtypedefpair<int,int>pii;typedefpair<double,double>......
  • 洛谷题单指南-分治与倍增-P7167 [eJOI2020 Day1] Fountain
    原题链接:https://www.luogu.com.cn/problem/P7167题意解读:从喷泉任意一个圆盘倒水,水流经的圆盘直径必须递增,水最后流到哪个圆盘。解题思路:1、枚举法有30%的数据范围在N<=1000,Q<=1000,因此枚举也可以得到30分。可以通过单调栈预计算每个圆盘后面第一个直径更大的圆盘位置Next[......