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: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; andN(≤500), the total number of gas stations. ThenNlines follow, each contains a pair of non-negative numbers:Pi, the unit gas price, andDi(≤D), the distance between this station and Hangzhou, fori=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, printThe maximum travel distance = XwhereXis 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

思路

这个问题的想法是在便宜的油站加尽可能多的油，昂贵的油站加尽可能少的油，具体操作是：每个站判断一次，如果站能到达更便宜的站，确保站，如果没有（也就是说，站是最便宜的），加油，然后选择第二个便宜的站补充油扩大范围。

通过代码

///最多安装水箱v,距离目的地skm，一个单位的气体车可以走perskm总共有n个站 ////每个站的气体价格p[i],距离杭州x[i] #include using namespace std; const double eps = 1e-8; #define Equ(a,b) ((fabs((a)-(b)))-eps) #define More(a,b) (((a)-(b))>eps) struct node{     double p,x; }nod[501]; bool cmp(node a, node b) {     return a.x < b.x;// } int main() {  double v, s, pers, price = 0, dis = 0, oil = 0, needoil;  int n;//n有多少站？  //v是水箱体积，s两站路程，pers是单位油能走多远  cin >> v >> s >> pers >> n;  for (int i = 0; i <= n - 1; i  ) {   cin >> nod[i].p >> nod[i].x;   getchar();  }  sort(nod, nod   n, cmp);  if (nod[0].x != 0 || n <= 0) {   printf("The maximum travel distance = 0.00");   return 0;  }  nod[n].p = 0;  nod[n].x = s;  double max = v * pers;////一次能走的最远距离  int i = 0;  int j = 1;  int min = j;  while (true) {   if (j > n) {    printf("%.2f", price);    return 0;   }   if (More((nod[j].x - nod[i].x), max)) {    printf("The maximum travel distance = %.2f", (dis   max));    return 0;   }   while (More(max, (nod[j].x - nod[i].x)) && j <= n) {    if (More(nod[i].p, nod[j].p)) {     min = j;     break;    }    else if (More(nod[min].p, nod[j].p)) {     min = j;    }    j  ;   }   j--;   needoil = (nod[min].x - nod[i].x) / pers;   dis = nod[min].x;   if (More(nod[i].p, nod[min].p)) {    if (MoreEqu(needoil, oil)) {     price  = (needoil - oil)*nod[i].p;                 oil=0;    }    }   else {    price  = (v - oil) * nod[i].p;//油加满    oil = v - needoil;   }   i = min;   j = i   1;   min = j;  }  return 0; }

总结

方法

1. 一开始，我想在整条路上选择最便宜的点，在这个点上加尽可能多的油，尽可能多地指的是满足和添加到终点，然后在最便宜的点的两侧选择最便宜的点重复操作，这样你就可以用递归解决。这个想法饶了我很久，还是只能部分正确(22/25)，放在这里有空再理解。(最绕的是start从以下代码可以看出，取多少代码正在频繁执行start 1-1操作）。由此可见，尽量不要在考场使用递归，你想不清楚的小弟弟wuwu~

   ///最多安装水箱v,距离目的地skm，一个单位的气体汽车可以走perskm总共有n个站 ////每个站的气体价格p[i],距离杭州x[i] #include using namespace std; const double eps = 1e-8; #define Equ(a,b) ((fabs((a)-(b)))-eps) #define More(a,b) (((a)-(b))>eps) struct node{     double p,x; }nod[501]; bool cmp(node a, node b) {     return a.x < b.x;// } double v, s, pers, dis = 0, oil = 0, needoil; double price = 0; int n;//n有多少站？ //v是水箱体积，s两站路程，pers是单位油能走多远 int canornot=1; int findprice(int start, int end, double oil) {  double max = v * pers;  double nodoil0, nodoil1;  int per;  if (start != 0) {   start  ;  }  int min = start;  for (int i = start; i < end; i  ) {   if (nod[min].p > nod[i].p) {    min = i;//找到最小   }  }  if (start != 0){
   		per = start-1;
   	}
   	else {
   		per = start;
   	}
   	if (nod[min].x - nod[per].x < max && nod[min].p>nod[per].p) {
   		nodoil0 = oil - (nod[min].x - nod[per].x) / pers;
   	}
   	else {
   		nodoil0 = 0;
   	}
   	if (nod[end].x - nod[min].x < max) {
   		nodoil1 = (nod[end].x - nod[min].x) / pers;
   	}
   	else {
   		nodoil1 = v;
   	}
   	price += (nodoil1 - nodoil0)*nod[min].p;
   	if (min - start >= 1) {
   		findprice(start, min, 0);
   	}
   	if (end - min > 1 && nod[end].x - nod[min].x > max) {
   		findprice(min, end, nodoil1);
   	}
   	else if (nod[end].x - nod[min].x > max) {
   		printf("The maximum travel distance = %.2f", (nod[min].x + max));
   		canornot = 0;
   	}
   	return price;
   }
   int main() {
   	cin >> v >> s >> pers >> n;
   	for (int i = 0; i <= n - 1; i++) {
   		cin >> nod[i].p >> nod[i].x;
   		getchar();
   	}
   	sort(nod, nod + n, cmp);
   	nod[n].p = 999;
   	nod[n].x = s;
   	findprice(0, n, 0);
   	if (canornot) {
   		printf("%.2f", price);
   	}
   	
   }

2. 然后来看一下某大佬的神仙思路，他是把路程存为数组，每次更新单位路程的最短价格，代码量少还好理解： https://blog.csdn.net/wangxianhualian/article/details/98976642

知识 

1. 如果记不得该引入什么库就：

   #include

   这里面包括了很多常用的库，一定要记下来，不多只能在拼题a上用，vs不行。

2.  

   #include 
   bool cmp(node a, node b)
   {
       return a.x < b.x;//将加油站照位置升序排列
   }
   int main(){
       sort(nod, nod + n, cmp);
       return 0;
   }

   这次用sort给struct node类型的结构排除，结果自定义了cmp却忘了写上，报的错又多又看不懂。

心态 

确实有点搞伤了这道题，以后记得先在草稿纸上用伪代码演算清楚再写代码，另外如果考试遇到这样的题一直不能全对就先放下来做别的，不要为一道题把脑子搞浆糊了。