/**//* 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
搜索
最新评论
|
|