我来说一下mega-kill的想法吧。这个想法比10楼的想法还要好,因为它可以找到一个解法。方法应该是对的,我也举了很多例子进行验证。
我们可以这样理解:每个站k给予一个数ak,为该站油量与到下一站需耗的油量的差。比如第三站存油5,到下一站耗油6,则a3=-1.
由题意,a1+a2....+an=0.
我们要证得是存在x,使ax,ax+a(x+1),ax+a(x+1)+a(x+2),。。。。。ax+a(x+1)+a(x+2)+。。。。。+an,ax+a(x+1)+a(x+2)+。。。。。+an+a1,
ax+a(x+1)+a(x+2)+。。。。。+an+a1+a2.....+a(x-1)均大于等于0。
再谈回mega-kill的想法。他的意思是找到一个站,开到此站时存油最少(不算该站将要加上的油)。那从这站出发,初始油量为0,接下去每站的油量都不会<0,即达到负值,应此可以环绕一圈。
然而,mega-kill在这里作了一个隐含的假设,因此导致我花了相当时间才发现关键所在:是否从任意一个站出发,油量最少的站都一致?要是从1出发,发现3站油最少,然后从3出发,发现4油最少,那mega-kill的想法就失去意义了。
幸好情况不是这样。假设从1站出发,在x站油量取到最小值即在a1,a1+a2,。。。。a1+a2+a3...+ax,。。。。a1+a2+a3....(an-1)+an=0中(1)a1+a2+a3....+ax<0最小,则有从a2出发的a2,a2+a3,a2+a3+a4,。。。。。a2+a3+.....+an+a1=0(1)中a2+a3......+ax最小,即同样在ax 取得最小值。
这个是可证的。如果(1)中最小的是a1+a2+a3....(an-1)+an=0,则显然从a1出发可跑完一圈,不然(2)中的最小值不是a2+a3+.....+an+a1=0就是a2+a3......+ax,于是任意从k出发,或者可以找到一种走法,或者最小站是固定的,而后者又可以推出存在走法。
PS:我这个证法说明某些情况下最小点未必固定,。也就是虽然可以走完,但楼主的方法未必适用。也许是作法疏漏或确实如此,我会进一步进行完善。