 /**//*
Jeep问题
http://en.wikipedia.org/wiki/Jeep_problem

http://topic.csdn.net/t/20020906/13/1001713.html

一车要穿越沙漠,距离为dist,油箱能装的油tank,每行走1单位耗油1单位
车可以行驶到中间一些位置,放一些油方便以后用再回去加油,起点有无限的油可以加
问最少耗的油走完这一段路

车的轨迹如下,假设中间有n个位置放了油

S ---->◆
<---
--------------->◆
<---------------
---------------------------------------->◆
<---------------------------------------
--------------------------------------------------------------------------> E
wiki上的说法是,假设油箱容量为1
第一次行驶1/(2n-1),然后在第一个加油站放1-2/(2n-1)的油,再用剩下的1/(2n-1)刚好回到S
以后的行驶中,行到第一个加油站时,加1/(2n-1)的油,所以油箱还满,然后再回到第一个加油站时,
取1/(2n-1),就能回到S了
所以S与第一个加油站的距离就是1/(2n-1)
而第二个加油站与第一个的距离,就是1/(2n-3)了 因为从第一个油站出发时油是满的,要被取2n-3次
第三个与第二个为1/(2n-5)
.
到了最后一个油站时,加油后就是满的,一直开完到E
所以最后一个油站离E为1
上图就说明,到达一个油站时,它的油肯定是满的(取走过来的各个油站的一些油填充这一路消耗的油)
答案就是,从E往S
走的距离1 + 1/3 + 1/5 + 1/(2n-1)
当然,S离第一个油站的距离可以小于1/(2n-1)

round up 是取上界

foj 1076一样的
另外一种jeep问题就是要求最后回到S的,走的距离1+1/2+1/3
*/
#include<iostream>
#include<cstring>
#include<map>
#include<algorithm>
#include<stack>
#include<queue>
#include<cmath>
#include<string>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<set>
#include<list>
#include<numeric>
#include<cassert>
#include<ctime>

using namespace std;


int main()
  {
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
#endif

double dist, tank;
scanf("%lf%lf", &dist, &tank);
double now = dist, cost = 0, pre;
int k = 1;
 while( (pre = now - tank / (2*k-1)) > 0) {
cost += tank;
now = pre;
k++;
}
cost += now * (2*k-1);
printf("%.0f\n", ceil(cost));
return 0;
}
|
|
常用链接
随笔分类
Links
搜索
最新评论

|
|