求大家帮忙看一道题

lapertem44

-   Acm改编：--------------------------------------------------------------------------------------
Problem
有一根m厘米的细木杆，杆上非始末端不同位置存在k个蚂蚁。蚂蚁的目标是全部从木杆上离开，但在细木杆上只会朝前走或调头而不能后退。当任意两只蚂蚁碰头时，会同时调头朝反方向走。假定木杆很细，只能同时通过一只蚂蚁；蚂蚁长度可忽略且每秒钟可以走1厘米的距离。

Input
本题给定数据为两行，第一行是整数m（25<m<100）；
第二行为k个整数（2<=k<=5），分别代表k个蚂蚁的位置；值代表离木杆始端的距离，若为正数则蚂蚁开始时头朝向末端，为负数则蚂蚁开始时头朝向始端。

Output
对于给定数据和规则，输出蚂蚁全部离开需要的秒数t及最后离开蚂蚁的初始位置值k（带正负号），用空格分开。

Sample Input
27
3 -7 11 -17 23

Sample Output
24 11

----------------------------------------------------------------------------------------------------------------------------------------------
我用python写的
现在只让返回时间先不考虑哪只最后离开

1. 
   
2. 
   
3. def ant(m,*args):
   
4.     t = 0
   
5.     x = []
   
6.     xx = [i for i in range(1,m)] #在木桥长度遍历
   
7.     temp = []
   
8.     #temp = (i for i in x if i in xx)
   
9.     count = len(temp)
   
10.     for arg in args:
    
11.         x.append(arg)
    
12.     num = len(x)
    
13.     #last = x[0]
    
14.     #return left
    
15.     while 1:
    
16.         if count != 1:
    
17.             x = [i+1 for i in x]
    
18.             t += 1
    
19.             temp = (i for i in x if abs(i) in xx)
    
20.             for j in range(0,num):
    
21.                 for k in range(0,num):
    
22.                     if j != k and abs(x[j]) == abs(x[k]):
    
23.                         x[j] = -x[j]
    
24.                         x[k] = -x[k]
    
25.         else:
    
26.             return t
    
27. 
    
28.         
    
29. 
    
30.         
    
31. #print (ant(10,-1,5))
    

复制代码

然后Shell就各种假死，我觉得没写错啊。
有哪位能帮忙看看或者示写一下给我参照参照的。万分感谢。

Linux_JinYuan

新人不懂
我没有看明白题意
是要输入一个值来模拟什么吗？

lapertem44

input
一个是 长度 比如例子中的 27（桥的长度）
一个是 蚂蚁的坐标

jeppeter

回复 1# lapertem44


    下面是我测试过的代码，你可以再测试一下，如果有错，告诉我。

1. def ValidateAnts(l,a):
   
2.         lastone = 0.0
   
3.         for v in a:
   
4.                 if abs(v) <= 0.0 or abs(v) >= l:
   
5.                         raise Exception('error input %d for long %d'%(v,l))
   
6.                 if abs(v) < abs(lastone):
   
7.                         raise Exception('input value %d or ascending order'%(v))
   
8.                 lastone = v
   
9. 
   
10. def AntSplit(l,a):
    
11.         lastone = 0
    
12.         totalsize = 0
    
13.         pos = list()
    
14.         # we assume first one to be select
    
15.         lastsel = 1
    
16.         ValidateAnts(l,a)
    
17.         for i in xrange(1,len(a)+1):
    
18.                 pos.append(i)
    
19.         cura = []
    
20.         for v in a:
    
21.                 cura.append(float(v))
    
22.         logging.info('a is %s'%(repr(a)))
    
23.         while len(cura) > 0 :
    
24.                 leastsize = l
    
25.                 lastv = cura[0]
    
26.                 if lastv < 0:
    
27.                         leastsize = abs(lastv)                       
    
28.                 for v in cura[1:]:
    
29.                         # if we have 2 value
    
30.                         # if we have the opposite direction
    
31.                         # so we calcuate the most size to step when
    
32.                         # we should test
    
33.                         if lastv >0 and v < 0:
    
34.                                 size = (abs(v) - abs(lastv))/2
    
35.                                 if size < leastsize :
    
36.                                         leastsize = size
    
37.                         lastv = v
    
38.                 if cura[-1] > 0:
    
39.                         size = l - abs(cura[-1])
    
40.                         if size < leastsize:
    
41.                                 leastsize = size
    
42.                 # now we do not met in the way
    
43.                 if leastsize == l:
    
44.                         if cura[0] > 0:
    
45.                                 # if it is the leftmost ,so it will
    
46.                                 lastsel = pos[0]
    
47.                                 # now to set the one
    
48.                                 totalsize += (l - cura[0])
    
49.                         else:
    
50.                                 lastsel = pos[-1]
    
51.                                 # now to set the step
    
52.                                 totalsize += (l + cura[-1])
    
53.                         break
    
54.                 logging.info('leastsize %f'%(leastsize))
    
55.                 # now to check for the
    
56.                 curb = []
    
57.                 lastone = cura[0]+leastsize
    
58.                 for i in xrange(1,len(cura)):
    
59.                         # now to modify the value
    
60.                         v = cura[i] + leastsize
    
61.                         if abs(lastone) == abs(v):
    
62.                                 # if we met ,so turn opposite
    
63.                                 lastone = -lastone
    
64.                                 v = -v
    
65.                         #logging.info('push %f into curb v %f'%(lastone,v))
    
66.                         curb.append(lastone)
    
67.                         lastone = v
    
68.                 # we append last one when nothing is on
    
69.                 #logging.info('push %f into curb'%(lastone))
    
70.                 curb.append(lastone)
    
71.                 assert(len(curb) == len(cura))
    
72.                 logging.info('len curb(%d) len cura (%d)'%(len(curb),len(cura)))
    
73.                 logging.info('curb %s'%(repr(curb)))
    
74.                 #assert(len(curb) == len(cura))
    
75.                 totalsize += leastsize
    
76.                 cura = []
    
77.                 for i in xrange(0,len(curb)):
    
78.                         v = curb[i]
    
79.                         if abs(v) > 0 and abs(v) < l:
    
80.                                 cura.append(v)
    
81.                         else:
    
82.                                 logging.info('delete %d %d'%(i,pos[i]))
    
83.                                 lastsel = pos[i]
    
84.                                 del pos[i]
    
85.                 logging.info('cura %s'%(repr(cura)))
    
86.                 logging.info('pos %s'%(repr(pos)))
    
87.                        
    
88. 
    
89.         return lastsel,totalsize

复制代码

这里解释一下代码，
   函数的输入参数是两个：
  1， l 就是你前面所说的长度
   2,  a,就是你所说的要输入的数列。
  这里的第11-22行是初始化一些参数，
  生成 cura表示是我们要处理的数列，这里把数据变成float类型，是更好的把你的问题变成可能是因为会出现0.5的数字处理。
  而pos就是一个数列，可以得到最后一个离开棒子的蚂蚁的初始位置
  

24-41 ：计算，不引起数据变化的最大长度，这里要满足两个条件：
          1， 没有蚂蚁走出棒子，换句话说，就是没有一个值abs(v) <= 0 or abs(v) >= l (棒子长度)
          2， 没有蚂蚁要转向。
         26-27 是因为，有可能最左边的蚂蚁是向左爬，那它可能不在棒子上，就是在最左边离棒子的距离。
         33-36 是计算，如果两个蚂蚁是相向而行，也就是在左边的蚂蚁向右，而在右边的蚂蚁向左，则它们会在多少时间相遇。
          38-41 是计算，如果最右边的蚂蚁向右爬，它可能不在棒子上，与最右边的距离。
         以上的计算，就是得到当前引起变化的最小距离。

43-53  前面的计算，可能会得到最大值就是棒子的长度，（现在来看，不会出现），这个时候，就是已经结束了。这个值就是所有的蚂蚁向一个方向，或者是向左，或者是向右，
          44-48 如果向右，则取最左边的蚂蚁距离最右端点的距离是步长。 而现在保留的最左边的蚂蚁当时的点就是最后一个蚂蚁的最初点。pos[0]
          49-53 如果向左，则取最右边的蚂蚁距离最左端点的距离是步长。 而现在保留的最右边的蚂蚁当时的点就是最后一个蚂蚁的最初点。pos[-1]


57-70 生成因为改变了，下一次迭代所有的蚂蚁的位置与方向信息。
         57 保留前一次，因为前一次，会与当前的有关系。
         59-67 生成下一次的蚂蚁位置与方向。
                   60 这个就是得到当前的蚂蚁的位置，因为这个蚂蚁如果是-7+2 表示向右，前进2，那位置就是-5
                   61 如果两个蚂蚁碰头。这个是前一个（就是左边的蚂蚁）与后一个（就是右边的蚂蚁）相遇了，这个时候，要它们转向。
                        所以， 这个时候，要修改原来的符号，这样就转向了。
          70 ，这个可能整个数据没有了，那就把最后一个加入。

75 加上了这一次引起变化，步长是多少。

76-85  这一次得到下一次迭代的蚂蚁位置。
         79-80 ，如果蚂蚁不在边界的位置（也就是在棒子的两头），则加入下一次的迭代。
          82-84 ，如果已经在边界的位置，则去除这个蚂蚁，它不在下一次迭代的范围内。
            83 是表示最后一个离开棒子的蚂蚁的初始位置，在while循环之外会有用。
            84 去除这个位置的信息，


上面的解释希望能对你有帮助。谢谢。         

jeppeter

回复 1# lapertem44


    如果要让上面的代码运行，请在所有的代码前面加上
    import logging

yinyuemi

回复 1# lapertem44


    http://bbs.chinaunix.net/thread-3575029-1-1.html

jeppeter

回复 1# lapertem44

1. def ValidateAnts(l,a):
   
2.         lastone = 0.0
   
3.         for v in a:
   
4.                 if abs(v) <= 0.0 or abs(v) >= l:
   
5.                         raise Exception('error input %d for long %d'%(v,l))
   
6.                 if abs(v) < abs(lastone):
   
7.                         raise Exception('input value %d or ascending order'%(v))
   
8.                 lastone = v
   
9. 
   
10. def AntSplit(l,a):
    
11.         lastone = 0
    
12.         totalsize = 0
    
13.         pos = list()
    
14.         # we assume first one to be select
    
15.         lastsel = 1
    
16.         ValidateAnts(l,a)
    
17.         for i in xrange(1,len(a)+1):
    
18.                 pos.append(i)
    
19.         cura = []
    
20.         for v in a:
    
21.                 cura.append(float(v))
    
22.         logging.info('a is %s'%(repr(a)))
    
23.         while len(cura) > 0 :
    
24.                 leastsize = l
    
25.                 lastv = cura[0]
    
26.                 if lastv < 0:
    
27.                         leastsize = abs(lastv)                       
    
28.                 for v in cura[1:]:
    
29.                         # if we have 2 value
    
30.                         # if we have the opposite direction
    
31.                         # so we calcuate the most size to step when
    
32.                         # we should test
    
33.                         if lastv >0 and v < 0:
    
34.                                 size = (abs(v) - abs(lastv))/2
    
35.                                 if size < leastsize :
    
36.                                         leastsize = size
    
37.                         lastv = v
    
38.                 if cura[-1] > 0:
    
39.                         size = l - abs(cura[-1])
    
40.                         if size < leastsize:
    
41.                                 leastsize = size
    
42.                 # now we do not met in the way
    
43.                 if leastsize == l:
    
44.                         if cura[0] > 0:
    
45.                                 # if it is the leftmost ,so it will
    
46.                                 lastsel = pos[0]
    
47.                                 # now to set the one
    
48.                                 totalsize += (l - cura[0])
    
49.                         else:
    
50.                                 lastsel = pos[-1]
    
51.                                 # now to set the step
    
52.                                 totalsize += (l + cura[-1])
    
53.                         break
    
54.                 logging.info('leastsize %f'%(leastsize))
    
55.                 # now to check for the
    
56.                 curb = []
    
57.                 lastone = cura[0]+leastsize
    
58.                 for i in xrange(1,len(cura)):
    
59.                         # now to modify the value
    
60.                         v = cura[i] + leastsize
    
61.                         if abs(lastone) == abs(v):
    
62.                                 # if we met ,so turn opposite
    
63.                                 lastone = -lastone
    
64.                                 v = -v
    
65.                         #logging.info('push %f into curb v %f'%(lastone,v))
    
66.                         curb.append(lastone)
    
67.                         lastone = v
    
68.                 # we append last one when nothing is on
    
69.                 #logging.info('push %f into curb'%(lastone))
    
70.                 curb.append(lastone)
    
71.                 assert(len(curb) == len(cura))
    
72.                 logging.info('len curb(%d) len cura (%d)'%(len(curb),len(cura)))
    
73.                 logging.info('curb %s'%(repr(curb)))
    
74.                 #assert(len(curb) == len(cura))
    
75.                 totalsize += leastsize
    
76.                 cura = []
    
77.                 delpos = []
    
78.                 for i in xrange(0,len(curb)):
    
79.                         v = curb[i]
    
80.                         if abs(v) > 0 and abs(v) < l:
    
81.                                 cura.append(v)
    
82.                         else:
    
83.                                 logging.info('delete %d %d'%(i,pos[i]))
    
84.                                 lastsel = pos[i]
    
85.                                 delpos.append(i)
    
86.                 while len(delpos) > 0:
    
87.                         i = delpos.pop()
    
88.                         del pos[i]
    
89.                 logging.info('cura %s'%(repr(cura)))
    
90.                 logging.info('pos %s'%(repr(pos)))
    
91.                        
    
92. 
    
93.         return lastsel,totalsize
    

复制代码

这里的代码有修正。
1，对于返回值，lastsel表明的是最后一个退出棒子的蚂蚁的最初位于棒子左边的第几个
2， 修改了delpos 这个是可以处理两个 以上被删除的点。
   

g361031315

来看看。。python还不是太好的说

zongg

好深啊，不会。

Linux_JinYuan

围观学习
好深奥~