首页 > 试题广场 >

大鱼吃小鱼

[编程题]大鱼吃小鱼
  • 热度指数:1513 时间限制: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 {
public:
    /**
     * 
     * @param N int整型 N条鱼
     * @param A int整型vector 每条鱼的体积为Ai
     * @return int整型
     */
    struct P{
        int x, t;
    };
    int solve(int N, vector<int>& A) {
        stack<P> S;
        int cnt = 0;
        for(int i=N-1;i>=0;i--){
            int t = 0;
            while(!S.empty() && A[i]>S.top().x){
                t = max(S.top().t, t+1);
                S.pop();
            }
            S.push({A[i], t});
            cnt = max(cnt, t);
        }
        return cnt;
    }
};

发表于 2020-09-01 00:49:16 回复(0)

class Solution {
public:
    /**
     * 
     * @param N int整型 N条鱼
     * @param A int整型vector 每条鱼的体积为Ai
     * @return int整型
     */
    int solve(int N, vector<int>& s1) {
        // write code here
        vector<int> s2;
        int count=0;
        int flag = 1;
        while (flag)
	{
		for (int i = 0; i < s1.size() - 1; i++)
		{
			if (i == 0)
			{
				s2.push_back(s1[0]);
			}
			if (s1[i] <= s1[i + 1])
			{
				s2.push_back(s1[i + 1]);
			}
		}
		if (s1.size() != s2.size())
		{
			count++;
			while (!s1.empty()) s1.pop_back();
			s1 = s2;
			while (!s2.empty()) s2.pop_back();
		}
		if (s1.size() == s2.size()  || s2.size()==1||s1.size()==1)
		{
			flag = 0;
		}
	}
		
	return count;
        
    }
};
您的代码已保存
运行超时:您的程序未能在规定时间内运行结束,请检查是否循环有错或算法复杂度过大。
case通过率为80.00%
发表于 2020-09-04 21:14:16 回复(0)
class Solution {
public:
    int solve(int N, vector<int>& A) {
        int n=A.size();
        vector<bool> life(n,true);
        int ret=-1;
        bool count=false;
        do
        {
            count=false;
            stack<int> st;
            for(int i=0;i<n;i++)
            {
                if(life[i] == true)
                {
                    if(st.empty() || A[st.top()] < A[i])
                    {
                        st.push(i);
                    }
                    else 
                    {
                        life[i]=false;
                        count=true;
                        while(!st.empty() && A[st.top()] > A[i])
                        {
                            st.pop();
                        }
                        st.push(i);
                    }
                }
            }
            ret++;
        }while(count==true);
        return ret;
    }
};

发表于 2023-09-28 15:03:33 回复(1)
#include <iostream>
#include <vector>
using namespace std;
#define Alive 0
#define Dead 1
class cute_fish
{
public:
    int value;
    int status;
    cute_fish()
    {
        value = 0;
        status = Alive;
    }
};

class Solution
{
public:
    vector<cute_fish> fish_vec;
    bool check_dead()//如果没有死鱼,就结束了
    {
        for (int i = 0; i < fish_vec.size(); i++)
        {
            if (fish_vec[i].status == Dead)
                return true;
        }
        return false;
    }
    void kill_fish()//类似于暴力破解,但是每轮都会清除死鱼,降低复杂度
    {
        for (int i = 0; i < fish_vec.size(); i++)
        {
            for (int j = i + 1; j < fish_vec.size(); j++) // j is i's right
            {
                if (fish_vec[i].value > fish_vec[j].value)
                {
                    fish_vec[j].status = Dead;
                    break;
                }
            }
        }
    }
    void only_alive()//只留下活的,降低复杂度
    {
        vector<cute_fish> temp_vec;
        for (int i = 0; i < fish_vec.size(); i++)
        {
            if (fish_vec[i].status == Alive)
                temp_vec.push_back(fish_vec[i]);
        }
        fish_vec.clear();
        fish_vec = temp_vec;
    }
    int solve(int N, vector<int> &A)
    {
        // write code here
        int fish_num = N;
        int ops = 0;
        for(int i=0;i<fish_num;i++)
        {
            cute_fish fish;
            // cin >> fish.value;
            fish.value=A[i];
            fish_vec.push_back(fish);
        }
        while (1)
        {
            kill_fish();
            if (check_dead())
            {
                ops++;
                only_alive();
            }
            else
                break;
        }
        return ops;
    }
};
// int main()
// {
//     Solution a;
//     vector<int> s = {4, 3, 2, 3, 2, 1};
//     a.solve(5, s);
// }
类似于暴力破解,循环kill()->check()->alive(),但是通过一些方法降低复杂度,详见注释
发表于 2023-04-03 23:29:30 回复(2)
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)
class Solution {
public:

    int solve(int N, vector<int>& A) {
        int len = A.size();
        for(int i= len -1;i>=1;i--)
        {
            if(A[i]<A[i-1])
            {
                A.erase(A.begin()+i);
            }
        }
        if(len ==A.size())
        {
            return 0;
        }
        return solve(N,A)+1;
    }
};
您的代码已保存
运行超时:您的程序未能在规定时间内运行结束,请检查是否循环有错或算法复杂度过大。
case通过率为80.00%



编辑于 2020-08-16 10:11:13 回复(0)
class Solution:
    def solve(self , N , A ):
        rst_count = 0
        while len(A) > 1:
            del_idx = []
            for i in range(len(A)-1):
                if A[i] > A[i+1]:
                    del_idx.append(i+1)
            if len(del_idx) != 0:
                count = 0
                for idx in del_idx:
                    del A[idx-count]
                    count += 1
                rst_count += 1
            else:
                break
        return rst_count

您的代码已保存
运行超时:您的程序未能在规定时间内运行结束,请检查是否循环有错或算法复杂度过大。
case通过率为80.00%
发表于 2020-08-15 17:45:47 回复(0)