| 個人檔案共享空间标题相片部落格清單 |  工具  說明 |
|
31 October 环形公路难题环形公路不均匀分布n个加油站，所有加油站的油加起来正好够一圈，油箱一开始为
空的，容量不限，且耗油均匀，问那个加油站出发可以跑完一圈 这个问题好像是via的c++笔试题目。我想了好久(~1h)，觉得:
其实这个问题可以衍生为:
1. 跑完全程的路线是否一定存在
2. 如果正向存在，反向是否一定存在
3. 怎么找到起点加油站，如果有很多起点都可以跑完，怎么找到所有的起点
我的解答参回复。谁有好的想法尽管发啊
======================================
仔细考虑了一下，我第一次回复的算法不妥，下班后在公交车上就开始想，到现在终于想到一个比较完满的做法
我们应该这样考虑 假设这个圆周上有4个点，分别是A,B,C,D
A1表示A这点油库可以跑的路程
A2表示A这点到下一点(B)的路程 令AA=A1-A2 依次类推,BB=B1-B2, CC=C1-C2, DD=D1-D2
到了最后,我们就有AA,BB,CC,DD四个数据
由于A1+B1+C1+D1=A2+B2+C2+D2, 所以有:
AA+BB+CC+DD=0 假设我们从A出发,能够顺利以D结束,我们就需要满足:
A1-A2>=0 (AA>=0) A1-A2+B1-B2>=0 (AA+BB>=0) A1-A2+B1-B2+C1-C2>=0 (AA+BB+CC>=0) 当然,上面只是假设.其实我们真正需要做的,是在AA,BB,CC,DD这四个数据中,找满足下面任意一种条件:
1. AA>=0 AA+BB>=0 AA+BB+CC>=0 2. BB>=0 BB+CC>=0 BB+CC+DD>=0 3. CC>=0 CC+DD>=0 CC+DD+AA>=0 4. DD>=0 DD+AA>=0 DD+AA+BB>=0 只要找到了,我们就可以从相关的点出发.比如我们找到满足条件3, 我们就可以从C点出发
好了,剩下来的方法就是如何高效地找到这个点.如果我们注意观察,其实算法很简单: 从AA开始,分别计算AA, AA+BB,AA+BB+CC. 如果其中某一次计算的结果<0, 直接跳到下一个数据.比如我们发现AA+BB+CC<0, 由于前面已经AA+BB>=0已经通过,所以CC必然<0, 由于CC<0, 我们肯定不能够用C作起点，所以我们就直接从CC的下一个数据,DD开始计算. 当找到可以满足条件的结果后,我们就找到了起点. 从这个算法可以看到,效率是o(n), 一次循环就搞定了.
当然,如果你还想提高效率,我们还可以做努力.我们假设AA,BB,CC,DD都不等于0, 也就是说他们或正或负。我们可以很简地得出，起点肯定是在由负变正的时候产生。所以我们在选择起点的时候，通过这个方法可以平均淘汰掉大约3/4的点 也就是说，算法可以表示如下: 1. 假设加油站分布在N1,N2..Nn点上，N1(1)表示N1这点油库可以跑的路程,N1(2)表示N1这点到下一点(N2)的路程,令NN1=N1(1)-N1(2),依次类推 2. 将NN1,NN2,..NNn放入环形链表中 3. 从NN1开始,计算NN1,NN1+NN2,...一直到NN1+NN2+..+NNn. 4. 在第三步,如果有NN1+NN2+..+NNx<0, 以NNx+1开始,重复第三步计算 5. 环形链表跑完以后,得到由NNx开始的所有计算结果>=0, 那么起点就是Nx这点 有人有兴趣用C来实现一把么? 回應 (13)
引用通告此內容的引用通告是： http://eparg.spaces.live.com/blog/cns!59BFC22C0E7E1A76!367.trak 引述這則內容的部落格
|
|
|
