题目:
班里N个小朋友,每个人都有自己最崇拜的一个小朋友(也可以是自己)。
在一个游戏中,需要小朋友坐一个圈,
每个小朋友都有自己最崇拜的小朋友在他的右手边。
求满足条件的圈最大多少人?
小朋友编号为1,2,3,...N
输入第一行,一个整数N(3<N<100000)
接下来一行N个整数(为9个小朋友,数字代表他们崇拜这列的第几个人),由空格分开。
要求输出一个整数,表示满足条件的最大圈的人数。
样式要求:
输入:
9
3 4 2 5 3 8 4 6 9
输出:
4
解决方案 一个圈就是从首到尾可以重复出现
我就抓住这个从重复出现入手
确定一个头一直崇拜下去,看崇拜链里是否有头。(应为最大崇拜数最多就是小朋友个数所以循环最大数就小朋友数+1)如果有就跳出循环并记录崇拜链长度存入列表。每个小朋友当一次头就结束循环,剔除列表里大于小朋友数的数选出最大的就是需要的解
Python代码:
x=int(input()) nums=map(int,input().split(' ')) box=[] for i in range(x): a=i#头的小朋友 sum=0#计数 for n in range(x+1): sum+=1 i=nums[i]-1 if i==a: break box.append(sum) box2=[] for i in box: if i<=x: box2.append(i) print(max(box2)) |
---|
实习主编 | 王楠岚
责 编 | 王自强