 /**//*
Jeep問題
http://en.wikipedia.org/wiki/Jeep_problem

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

一車要穿越沙漠,距離為dist,油箱能裝的油tank,每行走1單位耗油1單位
車可以行駛到中間一些位置,放一些油方便以后用再回去加油,起點(diǎn)有無限的油可以加
問最少耗的油走完這一段路

車的軌跡如下,假設(shè)中間有n個(gè)位置放了油

S ---->◆
<---
--------------->◆
<---------------
---------------------------------------->◆
<---------------------------------------
--------------------------------------------------------------------------> E
wiki上的說法是,假設(shè)油箱容量為1
第一次行駛1/(2n-1),然后在第一個(gè)加油站放1-2/(2n-1)的油,再用剩下的1/(2n-1)剛好回到S
以后的行駛中,行到第一個(gè)加油站時(shí),加1/(2n-1)的油,所以油箱還滿,然后再回到第一個(gè)加油站時(shí),
取1/(2n-1),就能回到S了
所以S與第一個(gè)加油站的距離就是1/(2n-1)
而第二個(gè)加油站與第一個(gè)的距離,就是1/(2n-3)了 因?yàn)閺牡谝粋€(gè)油站出發(fā)時(shí)油是滿的,要被取2n-3次
第三個(gè)與第二個(gè)為1/(2n-5)
.
到了最后一個(gè)油站時(shí),加油后就是滿的,一直開完到E
所以最后一個(gè)油站離E為1
上圖就說明,到達(dá)一個(gè)油站時(shí),它的油肯定是滿的(取走過來的各個(gè)油站的一些油填充這一路消耗的油)
答案就是,從E往S
走的距離1 + 1/3 + 1/5 + 1/(2n-1)
當(dāng)然,S離第一個(gè)油站的距離可以小于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
搜索
最新評(píng)論

|
|