首页 > 试题广场 >

大鱼吃小鱼

[编程题]大鱼吃小鱼
  • 热度指数:1519 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
牛牛最近喜欢上了俄罗斯套娃、大鱼吃小鱼这些大的包住小的类型的游戏。

于是牛爸给牛牛做了一个特别版的大鱼吃小鱼游戏,他希望通过这个游戏
能够近一步提高牛牛的智商。
游戏规则如下:

  • 现在有N条鱼,每条鱼的体积为Ai,从左到右排成一排。
  • A数组是一个排列。
  • 牛牛每轮可以执行一次大鱼吃小鱼的操作
  • 一次大鱼吃小鱼的操作:对于每条鱼,它在每一次操作时会吃掉右边比自己小的第一条鱼
  • 值得注意的时,在一次操作中,每条鱼吃比自己小的鱼的时候是同时发生的。
  • 举一个例子,假设现在有三条鱼,体积为分别[5,4,3],5吃4,4吃3,一次操作后就剩下[5]一条鱼。
    牛爸问牛牛,你知道要多少次操作,鱼的数量就不会变了嘛?
输出:表示要多少次操作,鱼的数量就不会变了
示例1

输入

3,[1,2,3]

输出

0

说明

不存在大鱼吃小鱼 
示例2

输入

6,[4,3,2,3,2,1]

输出

2

说明

[4,3,2,3,2,1]-->[4,3]-->[4] 

备注:
 
class Solution:
    def solve(self , N , A ):
        cnt=0
        split=0
        while len(A)>=2:
            tmp=[]
            for i in range(len(A)-1):
                if i==0:
                    tmp.append(A[i])
                if A[i]>A[i+1]:
                    continue
                else:
                    tmp.append(A[i+1])

            cnt+=1
            flag=False
            for i in range(len(tmp)-1):
                if tmp[i]>tmp[i+1]:
                    flag=True
                    break
            if not flag:
                break
            A=tmp
        return cnt


纯模拟,这里全通过了,但bilibili考卷那里是80%,有没有大佬懂
思路就是每次找到A[I]<=A[i+1]的分割点,不断缩小A,直到满足约束
发表于 2022-02-22 15:31:49 回复(0)
import sys
nums = int(sys.stdin.readline().strip())
line = sys.stdin.readline().strip()
a = list(map(int, line.split()))
a.reverse()
a.append(0)
times = 0 old = a while True:
    new = []
    flage = False  for i in range(1,len(old)): if old[i]>=old[i-1]:
            flage = True  continue  else:
            flage = True  new.append(old[i-1])
    old = new if flage:
        times+=1   if flage==False: break   print(times)
发表于 2020-09-04 22:09:12 回复(0)

问题信息

难度:
2条回答 5922浏览

热门推荐

通过挑战的用户

查看代码