• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

贮油点问题(C++)

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

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

描述 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 }
View Code

 

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

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


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
c/c++表达式求值发布时间:2022-07-13
下一篇:
C#同步、异步编程发布时间:2022-07-13
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap