穿越沙漠

Problem Description

一辆吉普车来到x公里宽的沙漠边沿A点，吉普车的耗油量为1升/公里，总装油量为500升。通常，吉普车必须用自身油箱中的油在沙漠中设置若干个临时储油点，才能穿越沙漠的。假设在沙漠边沿A点有充足的汽油可供使用，那么吉普车从A点穿过这片沙漠到达终点B，至少要耗多少升油。请编写一个程序，计算最少的耗油量（精确到小数点后3位）。

（1）假设吉普车在沙漠中行进时不发生故障；

（2）吉普车在沙漠边沿A点到终点B的直线距离为x≧500公里(即沙漠宽度)；

Input

输入的第一行含一个正整数k (1<=k<=6)，表示测试例的个数。后面紧接着k行，每行对应一个测试例，包含一个正整数x，表示从A点到B点的距离（1<=x<=2000）。

Output

每个测试例对应一行输出，包含一个数，表示最少的油耗量。

Sample Input

2

500

1000

Sample Output

500.000

3836.497

ps：真是一件很费脑力的好题啊，看题解都看了大半天0.0

分析：

按照第二个样例，起点到终点为1000km

我们逆着来，从终点开始考虑，

也就是从终点到起点中间的加油站分别为

l0（终点）…….l1…….l2……ln…

首先我们考虑是从I1到I0需要的油是500公升，也就是我们在I1的位置存放500公升的汽油才能保证车子到终点。

我们把两个I之间的距离写为S[i],耗油量为V[i]

则S1=500公里,V1=500公升

然后我们计算从l2到l1，很明显我们至少要从l2（l2->l1单向）开两趟车子才能在l1处储存500公升，那来回（两去一回）都计算上的话应该是至少3趟才行

能保证3次往返最低的总耗油量就是500公升（这一点很关键）

那么也就是说l2到l1之间的距离S2=500/3，l2到l0的距离是S1+S2=500+500/3

而同时在I2处的储存油量为：V2=500公升+500公升=1000公升

继续向下考虑，从I2到I3。要保证l2处有1000公升的汽油，我们必须要卡车最少从I3向I2开3趟（l3->l2单向），来回最少就是5趟。路上的总耗油量还是500公升，

那么l3到l2之间的距离S3=500/5，l3到l0的距离是S1+S2+S3=500+500/3+500/5

同时l3处的储存油量：V3=1500公升

由此推断：

如果i处需要储存油，那么就需要i*500的储存量。

车子从i+1处到i处（单向）至少要i次，往返总共是2*i-1次。

而这2*i-1次的最小总耗油量是500公升。

那么i+1与i之间的距离就是500/(2*i-1)。

假设A点到B点的距离为x，

最后i=n到开始点的距离是x-(S1+S2+S3+……+Sn)（也就是前面的总路程）

储油量：n*500

车子至少要从起点开n+1次满油到n处。加上返回的，一共是2n+1次。

而我们2n+1次的耗油量是（x-(S1+S2+S3+……+Sn)）*（2n+1）

所以，起点的油量就是Vn+（x-(S1+S2+S3+……+Sn)）*（2n+1）

Vn就是从ln点到终点总的需求油量

以上就是全部的分析过程了0.0

代码：

#include<stdio.h>int main(){int t;scanf("%d",&t);while(t--){double x;scanf("%lf",&x);if(x<=500)printf("%.3lf\n",x);else{int cnt=0;while(x>0){cnt++;x-=500*1.0/(2*cnt-1);}double ans=500*cnt*1.0+(2*cnt-1)*1.0*x;printf("%.3lf\n",ans);}}return 0;}