异想天开

What's the true meaning of light, Could you tell me why

加油站问题

日期:2014-09-14 00:12:46
  
最后更新日期:2014-09-15 23:23:04
【技术文章,非码农勿入】
题目描述:
有一环形赛道,上有若干个加油站,一辆小车希望从某个加油站出发绕一圈,路上要消耗油,加油站可以加油;已知加油站的总油量和路上消耗的油量一样多,并且小车最初没有油;试问是否可以从一个加油站出发,小车可以正常绕一圈?
题目分析: 这题是在微信的公共账号-趣味算法题 看到的。其实说白了也就是一个脑筋急转弯,当时脑袋没转过来。纠结于小车顺时钟和逆时针。后来突然发现顺时钟和逆时针是等价的。fuck,好久才开窍。被环形给坑了。假设给你一串数字 -3 2 -2 3这样,3后面又到第一个-3,即题目的环形。这里用一串来代替就是只考虑了顺时钟的情况,先考虑一个方向,后面发现逆时针方向也是一样。我们的目标是找到一个起点,该起点正数,然后一直累加为正或为0,直到最后一个数,那么最开始的这个数就是起点。两个数的时候,例如2 ,-2,容易确定2就是起点。三个数的时候,例如 1 -3 2也容易,合并2,1为3,变为3 -3也存在。没错,这里用数学归纳法,假设n个数成立,那么n+1个数呢? 记住对于题目的环形,现在只考虑一种方向,则转化为一个序列,最后一个数接第一个数,a1 a2 a3 ... 3 -2 ....。假设选择其中两个数,左边的为正数,右边为负数这种形式,且这两个数之和大于0,和并3和-2得到1,则满足n个数,存在一个数a满足题意。假设这个数就是1,那么n+1个数时,起点就是3。否则这个数不论是在1左边,还是右边,按从左到右的顺序,总是先遇到3,所以保证了时刻为正或0。因为先是假定了一种方向的,逆时针方向和顺时钟方向一样,还是可以排成从左到的右的序列。
题目的解法:
假设序列为a1,a2,a3 ... an。若a1累加到ak时,为负数,接下来从a(k+1)继续试探即可。一个循环即可判断出。