贮油点问题…..一道送命系列的递推…

描述 Description   

         一辆重型卡车欲穿过S公里的沙漠，卡车耗汽油为1升/公里，卡车总载油能力为W公升。显然卡车装一次油是过不了沙漠的。因此司机必须设法在沿途建立若干个贮油点，使卡车能顺利穿过沙漠。试问司机如怎样建立这些贮油点？每一贮油点应存储多少汽油，才能使卡车以消耗最少汽油的代价通过沙漠？

输入格式 Input Format

        仅一行，读入整数S,W(S<=1000,W<=500)。

输出格式 Output Format      

        编程计算及打印建立的贮油点序号，各贮油点距沙漠边沿出发的距离以及存油量(输出到小数点后第二位)。格式

如下：

?       0　　   0.00　　(dist)　　　　　　　　  ××(oil)

?       1　　   × ×  (dist)　　　　　　　　  ××(oil)

?       2　　   × ×　　　　　　　　　　　　××

?       …　　  ……　　　　　　　　　　　　……

注意：输出除了编号外距离和存油量均占10位。Pascal语言中表达为： Oir:10:2  Dist:10:2。

样例输入 Sample Input

1000 500

样例输出 Sample Output

0      0.00   3881.36

1     22.43   3500.00

2     60.89   3000.00

3    106.35   2500.00

4    161.90   2000.00

5    233.33   1500.00

6    333.33   1000.00

7    500.00    500.00

我最开始连题都读不懂…..怎么可能会写……直到有一天一个dalao告诉我说我校oj有题解，于是就去读了题解写完的…..感谢那个撰写题解的dalao….

首先声明一下这个题的题意…..(看了dalao题解思路才懂)：

车子想要穿过沙漠，但是储油点是自己建立的

比如样例1

0　　  0.00   3881.36

就是说，自己在起点建立一个有 3881.36L的油点

然后跑向  22.43  这个储油点，一共跑了17次，一共卸下了3500L的油，消耗了381.36L的油

然后把剩下的3500L的油继续运向下一个储油点……

也就是说，车子是边走边建立储油点的，车子离开的时候，每个储油点的油都被运到了下一个储油点，到最后车子离开沙漠，油全部用完，储油点空空如也。

然后就是题解了：

  如果从起点出发顺推,则我们无法确定第一个贮油点的位置及贮油量,因此我们可以用倒推法来解决这个问题：先从终点出发倒推最后一个储油点的位置及储油量,然后再把最后一个储油点作为终点,倒推倒数第二个储油点的位置及储油量。

  因为题目中要求找最少的耗油，也就是说，最后一个储油点的位置离终点的距离就是汽车一次能行驶的距离，这样就可以直接装满油走了。那么我们就可以确定了最后一个储油点的位置，就是总路程s减去汽车油箱大小w，存储的油就是w。

  然后根据最后一个储油点向前推，因为要在当前储油点运送w的油，而中途汽车运油的时候，还会消耗油量，那么就需要w*2的油，而储油点距离当前储油点的距离就是汽车消耗w油所走的路程除以来回的次数。

  注意，最后一个点也就是最开始的点需要特判，手动赋值。

  PS：发现从后往前每次运油的来回次数都是从1开始每次+2,（因为每次多运了w油，所以多走一个来回）。

那么我们用ai[p]表示最后一个点的距离，bi[p]表示最后一个点的油量,x表示来回数

则有：  ai[p-1]=ai[p]+w;

             bi[p-1]=ai[p]-w/x;

这样我们就可以用循环来AC这道题了

代码如下：

 1 #include <iostream>
 2 #include <iomanip>
 3 #include <cstdio>
 4 #include <cmath>
 5 #include <cstring>
 6 #include <algorithm>
 7 #include <ctime>
 8 using namespace std;
 9 long long p=1,l,x=1,q=0,t=0;
10 double s,w,zb[10086],yl[10086],d=0,cb[10086],cy[10086];//zb是逆推时存距离的，cb用来存储距离，方便后面倒着输出,yl存储逆推时的储油量，cy记录yl，同样为了方便倒着输出
11 int main(){
12     cin>>s>>w;
13     zb[1]=s-w;
14     yl[1]=w;
15     d=w;//d是储油点的距离
16     while(d!=0) {//逆推得不到0，所以只要!=0就推就好了//自然是可以直接大于0的...这样下面那行<0的特判就不必要了...dalao可以尝试下，反正我失败了、。。。
17         q++;//q是循环的次数
18         x+=2;
19         l=p;
20         yl[p+1]=yl[p]+w;
21         zb[p+1]=zb[p]-w/x;
22         d=zb[p];
23         if(d<0){//但是会出现小于0的情况，这是我们直接结束循环即可
24             p--;
25             break;
26         }
27         cb[p]=zb[p];
28         cy[p]=yl[p];
29         p++;
30     }
31     cb[p+1]=0.00;//最后一组距离为0.00的情况需要特判
32     cy[p+1]=yl[p]+zb[p]*x;
33     for(int i=q;i>=1;i--){
34         cout<<setiosflags(ios::fixed)<<setprecision(2);
35         cout<<t<<' '<<cb[i]<<' '<<cy[i]<<endl;
36         t++;//t表示储油点的序号,从0开始
37     }
38     return 0;
39 }

PS:网上的贮油点问题大多没有完整的通俗易懂的代码……发出来造福群众……

PS:看代码AC就看代码AC了吧……反正对于敲程序的人没有任何益处，对我也没有任何坏处……