贮油点问题(C++)

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

描述 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这道题了

代码如下：

 #include <iostream>

 #include <iomanip>

 #include <cstdio>

 #include <cmath>

 #include <cstring>

 #include <algorithm>

 #include <ctime>

 using namespace std;

 long long p=,l,x=,q=,t=;

 double s,w,zb[],yl[],d=,cb[],cy[];//zb是逆推时存距离的，cb用来存储距离，方便后面倒着输出,yl存储逆推时的储油量，cy记录yl，同样为了方便倒着输出

 int main(){

     cin>>s>>w;

     zb[]=s-w;

     yl[]=w;

     d=w;//d是储油点的距离

     while(d!=) {//逆推得不到0，所以只要!=0就推就好了//自然是可以直接大于0的...这样下面那行<0的特判就不必要了...dalao可以尝试下，反正我失败了、。。。

         q++;//q是循环的次数

         x+=;

         l=p;

         yl[p+]=yl[p]+w;

         zb[p+]=zb[p]-w/x;

         d=zb[p];

         if(d<){//但是会出现小于0的情况，这是我们直接结束循环即可

             p--;

             break;

         }

         cb[p]=zb[p];

         cy[p]=yl[p];

         p++;

     }

     cb[p+]=0.00;//最后一组距离为0.00的情况需要特判

     cy[p+]=yl[p]+zb[p]*x;

     for(int i=q;i>=;i--){

         cout<<setiosflags(ios::fixed)<<setprecision();

         cout<<t<<' '<<cb[i]<<' '<<cy[i]<<endl;

         t++;//t表示储油点的序号,从0开始

     }

     return ;

 }

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

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

巴特西

贮油点问题(C++)

最新文章

热门文章