蓝桥杯算法训练VIP-旅行家的预算

题目

题目链接

题解

贪心。

贪心思路：

再次更新，2022.4.15 做PTA时发现一道类似的题目，看了题解发现，下面的思路不对。 策略中有一点要注意的，如果下一个能到达的加油站中，有多个加油站比当前加油站便宜，不是选择最便宜的那个，而实选择离当前加油站最近的那个（尽管这个加油站不是最便宜的） 因为我们完全可以先到达比较便宜的加油站，再到达最便宜的加油站，这样一定比直接从当前加油站到最便宜的加油站要划算。

更新于2022.4.3 本来以为之前的思路出现问题了，结果发现没问题……

以下所说的加油站忽略最后一个，即忽略终点，终点用于特殊判断。

（当前加油站处车的油量任意，即不影响我们后续的决策）
	
从当前加油站开始向后找加油站：
 	1. 若没有能到达的加油站（所谓“能到达”就是指加满油后可达），则进行下面的判断：
 		(1) 无法到达终点，则直接No Solution；
		(2) 可以到达终点，则直接到达终点。
	2. 若有能到达的加油站，：
 		(1) 若找能到达的加油站中油价最低的加油站的油价比当前的加油站油价低，则选择这个加油站作为目的地，油量加到刚好能到达找到的加油站即可；
  		(2) 若这个加油站的油价比当前的加油站油价高，则判断是否能直接到达终点：
  				① 若能直接到达终点，则直接到达终点；
 				② 若不能直接到达终点，则在当前加油站加满油，将找到的加油站作为目的地。

以下所说的加油站忽略最后一个，即忽略终点，终点用于特殊判断。

从能能到达的加油站中选一个油价最低的加油站进行判断：
  	若没有能到达的加油站：
  		无法到达终点，则直接No Solution；
   		可以到达终点，则直接到达终点。
   	若有能到达的加油站：
   		若这个加油站的油价比当前的加油站油价低，则选择这个加油站作为目的地，油量加到刚好能到达找到的加油站即可；
   		若这个加油站的油价比当前的加油站油价高，则判断是否能直接到达终点：
   			若能直接到达终点，则直接到达终点；
   			若不能直接到达终点，则在当前加油站加满油，将找到的加油站作为目的地。

理解性地讲述一下： 肯定是要找便宜的加油站，但是这个所能到达的最便宜的加油站的油价有可能比当前所在的加油站的油价贵。贵的话，我们就直接在当前加油站加满油，尽量在那个虽然比较便宜但是仍比当前加油站贵的加油站少加点油，省点钱。如果最便宜的加油站比当前的便宜，那我只要把油加到刚好能到那里的量即可，之后的油可以到了便宜的加油站再加，要是在当前加油站加多了直接血亏。 如果前面的加油站我都到不了，我完蛋了，根本不可能到达终点。只要看我油箱全部加满能不能到达某个加油站就能判断我还是不是能前进了。 还有小细节，比如我要是前面能到的加油站中最便宜的也比我当前的贵，但是我可以在当前加油站加满，一口气直接开到终点，那么我也完全没必要在中间的加油站停留。

注意四舍五入： (int(a*100+0.5))/100.0 对a进行保留小数点后两位的操作。

代码

/*
代码中的部分注释通过代号 step? 简略表示

step1：从能到达的加油站中选一个油价最低的加油站进行判断 
step2：若没有能到达的加油站，且到不了终点则直接No Solution；
step3：若没有能到达的加油站，但能到终点则直接到达终点
step4：若有能到达的加油站，且这个加油站的油价比当前的加油站油价低，则选择这个加油站作为目的地，油量加到刚好能到达找到的加油站即可 
step5：若有能到达的加油站，但这个加油站的油价比当前的加油站油价高，则判断是否能直接到达终点
step6：若能直接到达终点就到达终点；
step7：若不能直接到达终点则在当前加油站加满油，前往找到的加油站 

*/
#include
using namespace std;

int n;
double des, c, unitdist, sp, rest, cost;

struct node {
	double pos, p;
} oil[100];

bool cmp(node a, node b) {
	return a.pos >des>>c>>unitdist>>sp>>n;
	oil[0].p = 100; // 设置为极大值 
	oil[1].pos = 0; oil[1].p = sp; n++;
	for(int i = 2;i >oil[i].pos>>oil[i].p;
	
	int t = 1;
	while(t  c) {puts("No Solution"); return 0;} // step2
			else {cost += ((des-oil[t].pos)/unitdist - rest)*oil[t].p; break;} // step3
		}
		
		if(oil[pos].p