吉普车试图穿越 x km 宽的沙漠,吉普车耗油率1L/km,总装油量 500L,对于 x > 500,吉普车需要设置临时储油点,以穿越沙漠。现在,我们需要对于输入的 x 值,计算最少的耗油量。其中, 0 ≤ x ≤ 3000.
在思考这道题之前,我们先考虑几个常识性问题:
1、越往沙漠深处的储油点送油,所消耗的油量更多(在往返的路上必然会消耗更多的油量)
2、要使总耗油量最少,那么需要使得绝对单位路径上的长度最小。
(其中,绝对路径指完全行驶的距离,即不再需要返回。)
3、要使得耗油量最少,那么我们需要满足以下条件:
a、每次车应该满载而去,空载而归。
b、从第 i 个储油点将油送到第 i + 1个必然消耗的比从起点而始耗油量要少。
c、在到达终点的时候,必然有:所有储油点、车上的油量均为0。
d、储油点存储的油量必然是500的整数倍——这一点可由 3.a 推得。
4、考虑将油从第 i 个储油点送至第 i + 1个的过程:假设需要送 n 趟,那么在最后一趟时,吉普车到达第 i + 1个储油点时,这时候,吉普车将没必要回到前面的储油点,假设这期间的距离为d,那么所在运输中所消耗的油量为 (2n - 1)d。
现在,我们有充足的知识储备来解决这道题了。
1、根据常识1,最后一个储油点应该设置在离终点500km的地方,此时耗油量最少,同时,考虑到在此时车会直接载满油冲向终点,那么最后一个储油点需要500L油。
2、我们倒推到第二个储油点。不过在这之前,我们需要证明:若在运输油的途中,若两个储油点间单位路径耗油量最少,那么需要将油从第 i 运输到第 i + 1个储油点的途中,需要吉普车满载的次数最少。
证明如下:假设满载次数为 n ,同时第 i + 1 个除油站需要 500c 的油量,那么由在途中的往、反累计 2n - 1 次——其中由于在最后将不会回返。那么设期间距离为 d,那么易得,进而得出:
,而单位路径耗油量将以500(n - c)除以这个值,从而得到这两个储油点间单位路径耗油量为 2n - 1。(注意:我们计算的储油点的油存储量并非仅仅单个储油点的存储量,而同时包括了后续油站的存储量)显然其为n的线性函数,那么n在最小值时将取得最大值——这与路径长度无关。
而最后一个储油点需要500L的油量,那么从倒数第二个储油点出发应该至少满载两次——行驶途中必然会消耗油量。那么带入 n = 2, c = 1,得到 d = 500/3,而两次满载,也就意味着从第倒数二个储油点需要1000L的汽油——即能够支持从第倒数二个储油点到终点的汽油量。
同时,我们继续向后推,便得到倒数第三个储油点需要至少满载3次,而得到距离 d =500/5 = 100km,同时我们也能得出它需要1500L汽油支持从其到终点。
那么,显然的,我们可以观察出,在两个储油点之间 n - c = 1恒为常数,而 n 与倒数第 i 个储油点的 i 值成正相关,那么从终点到由终点起开始计数的第 n 个储油点的距离为:,而该数列显然发散,因此可以从出发点走到终点。
现在,考虑在从终点开始数的最后一个储油点——它可能会多出一段并不属于该数列中的长度,我们假设它的储油点数目是n,那么由之前的推论可得,它需要500n的油量以支持从该处到达终点。同时,我们有从起点到该处的距离为:。
那么起点需要的满载的次数满足:,那么起点的满载次数为:
,那么所需要的油量就为:
以下是C语言实现:
#pragma warning(disable : 4996)
#include<stdio.h>
int main(void)
{
int x, count = 1;
double oil, dis = 500; //count代表储油点的编号,同时dis表示终点前的距离
scanf("%d", &x);
if (x <= 500)
oil = x;
else
{
do
{
++count;
dis += 500 / (2 * count - 1);
oil = 500 * count;
} while (dis < x);//退出循环时,dis >= x,同时储油点的数量正确
oil = 500 * count + (x - dis) * (2 * count - 1);
//此处的运算思路与我的不同——程序运用了油量必须用完的条件,
//使得条件式:总耗油量油量 = 第一个储油点的油量加上路径上消耗的油量
//其中,由于最后一次小于1/(2n + 1),因此其满载次数不变。
}
printf("%.2f\n", oil);
return 0;
}