P1347 To Fill or Not to Fi - 题解

登录注册上岸

以下题解仅供学习参考使用。

抄袭、复制题解，以达到刷AC率/AC数量或其他目的的行为，在N诺是严格禁止的。

N诺非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看N诺社区规则。

2024年3月20日 21:18

思路解析与代码实现（相对精简，参考了前辈们的题解）

P1347

回复 0 | 赞 1 | 浏览 583

已知油箱初始为空，设有 n 个加油站（按距起点由近到远排序，编号 1...n）。则 no.1 必然要在起点，车才能出发。再令终点为 no.n+1。假设在 no.i 加满油，到达 no. i+1 时，会消耗掉 from i to i+1 这段距离对应的油量，这些油耗只能来自在 no.i 装满的油箱。如果满油箱也支持不了 from i to i+1 的耗油，那能到的最远距离就是 “no.i 距起点的距离” + “满油箱能走的距离”。为使花费最...

2023年7月19日 21:10

基于大佬代码的更加清晰的版本（高强度注释）

P1347

回复 0 | 赞 2 | 浏览 1.2k

/* 我们假设会经过所有的加油站我们可以假装持有价格高得油，一旦遇到价格低的就进行替换在经过加油站的时候，我们补充该加油站的油（注意是假设补充，具体是否补充要看之后有没有遇见更加便宜的油）比如，我们的油箱在遇到价值4快的加油站时，还剩下2块钱的油和5块钱的油，这说明之前假装补充的5块钱的油是可以被四块钱的油所替代，因此我们就可以补充油注意计算cost的时候要以实际花费的油为准，而不是在补充油的时候进行计算 */ #include<bits/stdc++.h> using namespace std; // double判断相等需要...

2021年5月20日 15:27

借鉴题解里的大佬的代码；自己加了一些注释方便读懂；留备复习用

P1347

回复 1 | 赞 2 | 浏览 8.6k

#include<bits/stdc++.h> using namespace std; //加油站 struct Station{ double price;//单位油价 double dist;//该加油站距离杭州距离 }; //最后输出打印 struct Print{ int flag;//是否到达 double pri;//若到达此处为how much；若未到达此处为how far has run }; //按照距离杭州最近的排序 bool cmpD(Station a, Station b){ return a....

2022年3月17日 15:16

P1347

回复 0 | 赞 0 | 浏览 5.3k

#include<cstdio> #include<algorithm> using namespace std; const int INF =1000000000; struct Station{ double p, dis;//单位油价，距起点距离 }sta[510]; 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...

2022年1月27日 09:40

可能是最清晰和通用的思路

P1347

回复 0 | 赞 3 | 浏览 6.7k

通用解法思路:首先在经过每个加油站时，都要确保油箱是满的。我们将不同加油站的油看成是一份加入到油箱中。利用双端队列维护油箱，双端队列的前端装价格低的油，后端装价格高的油。在从加油站i-1驶向加油站i的过程中，优先使用队列前端的油，并进行价格的累加。每经过一个加油站，将该加油站的油价和队列中的油价进行对比，弹出队列中比该加油站价格高的油，然后用该加油站的油填满油箱剩余部分。以上贪心策略保证了价格低的油可以最先被使用。另外需要注意的一点是，double类型的数字之间，由于精度问题，需要引入eps进行比较。注意以上策略可以处理油站所在的位置以及cmax,d,da...

2020年6月11日 17:26

太难了，摸索了一下午算是折腾出答案来。（不完善）

P1347

回复 0 | 赞 1 | 浏览 10.3k

先占个坑，后面有想法了再来改进。（对我而言，难点就在于，在当前的加油站点下，怎么查找，并判断剩下的站点，然后进行选择。总体思路就是。分情况在油箱满能到达的范围，寻找，1，在第一次找到比当前油价抵得时候，跳出，去到此点，更新当前站点指针， 2，没有比当前低，则找寻相对最低的。后面就是循环，之前曾陷入误区，认为起始点加油站和后面不一样，其实是是一样的。举个例子，假设，我从起点1号加油站出发，在油箱满油范围内找不到比当前更低油价加油站，则需要加满油，那么到达2号站点后...

2020年2月26日 22:50

感觉相对来说我这个还简单点就写个题解

P1347

回复 0 | 赞 1 | 浏览 9.3k

核心代码就是Loop函数里面for循环的内容了，加起来10行多一点，应该算比较简单吧~~（大概） struct node { double price; double dist; }; struct print { int flag; double pri; }; bool cmpD(node a, node b) { return a.dist <= b.dist; } print Loop(int cmax, int davg, int num, double ...

题目To Fill or Not to

题解数量7

热门题解

1 可能是最清晰和通用的思路

2 借鉴题解里的大佬的代码；自己加了一些注释方便读懂；留备复习用

3 基于大佬代码的更加清晰的版本（高强度注释）

4 感觉相对来说我这个还简单点就写个题解

5 太难了，摸索了一下午算是折腾出答案来。（不完善）

6 思路解析与代码实现（相对精简，参考了前辈们的题解）

7 详细解答