首页 > 试题广场 >

大雨吃小鱼

[编程题]大雨吃小鱼
  • 热度指数：588 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解

小明最近喜欢上了俄罗斯套娃、大鱼吃小鱼这些大的包住小的类型的游戏。

于是小明爸爸给小明做了一个特别版的大鱼吃小鱼游戏，他希望通过这个游戏

能够近一步提高牛牛的智商。

游戏规则如下：

现在有N条鱼，每条鱼的体积为Ai，从左到右排成一排。

A数组是一个排列。

小明每轮可以执行一次大鱼吃小鱼的操作

一次大鱼吃小鱼的操作：对于每条鱼，它在每一次操作时会吃掉右边比自己小的第一条鱼

值得注意的时，在一次操作中，每条鱼吃比自己小的鱼的时候是同时发生的。

举一个例子，假设现在有三条鱼,体积为分别[5，4，3]，5吃4，4吃3，一次操作后就剩下[5]一条鱼。

爸爸问小明，你知道要多少次操作，鱼的数量就不会变了嘛？


输入描述:
给定N；
给定A数组
１＜＝N＜＝１０＾５
１＜＝Ai＜＝Ｎ


输出描述:
一行, 正整数, 表示要多少次操作，鱼的数量就不会变了。
示例1

输入

3
1 2 3

输出

0
示例2

输入

6
4 3 2 3 2 1

输出

2

说明

[4,3,2,3,2,1]-->[4,3]-->[4]
算法知识视频讲解
添加回答
maoxiaomao头像 maoxiaomao
循环提取非递增数组(提取一次非递增数组实际上就是模拟一次吃鱼过程)，计算器加1
直到不能提取非递增数组为止(实际上就是不能吃鱼了)，跳出循环，程序结束 
N=input().strip().split()
A=list(map(int,input().strip().split()))
c=0
i=0
while(1):
    t=[]
    while i<len(A):
        t.append(A[i])
        while i+1<len(A) and A[i+1]<A[i]:
            i=i+1
        i=i+1
    if len(A)!=len(t):
        c=c+1
    else:break
    i=0
    A=t
print(c)


编辑于 2021-05-24 14:53:41 回复(0)
pein531头像 pein531
直接模拟，其实就是进行操作：每次保留整个数组中所有递减序列的第一个元素。直到数组的长度不再改变为止。 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        String[] strFish = br.readLine().trim().split(" ");
        ArrayList<Integer> fish = new ArrayList<>();
        for(int i = 0; i < strFish.length; i++)
            fish.add(Integer.parseInt(strFish[i]));
        ArrayList<Integer> newFish = descSize(fish);
        int count = 0;
        while(!newFish.isEmpty() && newFish.size() < fish.size()){
            count ++;
            fish = new ArrayList<Integer>(newFish);
            newFish = descSize(fish);
        }
        System.out.println(count);
    }
    
    private static ArrayList<Integer> descSize(ArrayList<Integer> list) {
        ArrayList<Integer> newList = new ArrayList<Integer>();
        int i = 0;
        for(; i < list.size() - 1; i++){
            if(i == 0)
                newList.add(list.get(i));
            if(list.get(i) <= list.get(i + 1))
                newList.add(list.get(i + 1));
        }
        return newList;
    }
}

发表于 2021-04-11 22:53:34 回复(0)
牛客713798835号头像 牛客713798835号
# number = list(map(int, input().split()))  # 把输入直接转成数字


import cProfile
import copy

MOD = 1e+3


# 定义input辅助函数（从文件加载模拟输入）
class InputHelper:
    def __init__(self, path="./input_data.txt"):
        with open(path) as file:
            self.lines = file.readlines()
        self.currentLine = -1

    def getInput(self):
        self.currentLine += 1
        return self.lines[self.currentLine]


# 定义处理函数
def solver(N, nums):
    nums_before = copy.copy((nums))
    nums_after = []
    last_nums_after_len = 0
    play_times = 0
    if len(nums_before) == 0:
        return 0

    i = 0
    while (1):
        while i < (len(nums_before)):
            nums_after.append(nums_before[i])
            while i + 1 < len(nums_before) and nums_before[i] > nums_before[i + 1]:
                i += 1
            i += 1
        # print(last_nums_after_len)
        if len(nums_before) == len(nums_after):
            break
        else:
            play_times += 1
           
        nums_before = nums_after
        nums_after = []
        i=0
    return play_times


def main(get_input=input):
    # N,M=map(int,get_input().split())
    N = int(get_input())
    nums = list(map(int, get_input().split()))
    print(solver(N, nums))
    pass


if __name__ == '__main__':
    using_input_helper = False
    if using_input_helper:
        inputHelper = InputHelper()
        cProfile.run("main(inputHelper.getInput)")  # test with performance monitor
        # main(inputHelper.getInput)  #test without performance monitor
    else:
        # cProfile.run("main()")  #test with performance monitor
        main()  # test without performance monitor

发表于 2022-04-20 14:37:01 回复(0)
OfferOffer你要去哪里呀头像 OfferOffer你要去哪里呀

双数组

#include 
using namespace std;
const int N = 1e5 + 5;
int pre[N], aft[N];
int n, m;

int main() {

    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        scanf("%d", &pre[i]);
    }

    int ans = 0;
    while(n > 1) {
        aft[m++] = pre[0];
        for (int i = 1; i < n; i++)
            if (pre[i] > pre[i - 1])
                    aft[m++] = pre[i];

        if (m == n) break;
        ans++;
        n = m;
        m = 0;
        memcpy(pre, aft, sizeof aft);
    }
    printf("%d\n", ans);
    return 0;
}
发表于 2022-01-16 23:08:33 回复(0)
henryboy233头像 henryboy233 
N = int(input())
A = list(map(int,input().split()))
ans = 0
i = 0
while (1):
    temp = []
    while i < len(A):
        temp.append(A[i])
        while i + 1 < len(A) and A[i + 1] < A[i]:
            i += 1
        i += 1
    if len(temp) != len(A):
        ans += 1
    else: break
    i = 0
    A = temp
print (ans)

发表于 2021-12-06 15:05:32 回复(0)
phoenixAspies头像 phoenixAspies
用单调栈 一遍循环直接出结果，时间复杂度O(n) 
#include <bits/stdc++.h>
using namespace std;
int main() {
    stack<int> priority_stack;
    int N(0);
    cin >> N;
    priority_stack.push(-1);
    int opers(0), currentMaxPos(-1), currentSecondMax(-1);
    int current_opers(1);
    bool isOper = false;
    vector<int> fishes(N + 1, 0);
    for (int it = 1; it <= N; ++it) {
        cin >> fishes[it];
        if (fishes[it] >= fishes[it - 1]) {
            if (fishes[it] < priority_stack.top()) {
                if (fishes[it] >= currentSecondMax) {
                    ++current_opers;
                    currentSecondMax = fishes[it];
                    currentMaxPos = it;
                }
            }
            else {
                opers = max(current_opers, opers);
                current_opers = 1;
                currentMaxPos = -1;
                currentSecondMax = -1;
                while (fishes[it] < priority_stack.top()) {
                    priority_stack.pop();
                }
                priority_stack.push(fishes[it]);
            }
        }
        else {
            isOper = true;
        }
    }
    opers = max(current_opers, opers);
    if (!isOper and opers == 1) opers = 0;
    cout << opers<< endl;
    return 0;
}


发表于 2021-08-25 18:07:17 回复(0)
头大的烦恼头像 头大的烦恼 
/**
  * 解题要点
  * 1 - 连续递减：动态规划
  * 2 - 结束条件：使用一个bool的标志位
  * 3 - 怎么删除：使用辅助数组
  */

#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;

int main()
{
    // 1 - 读取数据
    int N;
    cin>>N;
    vector<int> A(N, 0);
    for(int i=0; i<N; i++)  cin>>A[i];
    vector<bool> isDelte(N, false);

    // 2 - 计算操作次数
    int res = 0;
    while(1){
        // 3 - 动态规划，找出递减的子序列，并做大鱼吃小鱼的操作
        int left=0, right = 0;
        int lastVal = -1;
        bool  flag = true;
        while(right<N){
            if(isDelte[right]){  // 已经删除，跳过
                right++;
                //cout<<"(2)"<<"isDelte:"<<right<<endl;
            }else if(lastVal > A[right]){ // 递减子序列
                lastVal = A[right];
                right++;
                flag = false;
            }else{
                // 4 - 模仿大鱼吃小鱼
                for(int i=left+1; i<right; i++) isDelte[i] = true;
                left = right;
                lastVal = A[left];
                right++;
                //cout<<"(1)"<<"right:"<<right<<endl;
            }
        }
        for(int i=left+1; i<N; i++) isDelte[i] = true;

        if(flag) break;
        else     res++;
    }

    // ? - 输出结果
    cout<<res<<endl;

    return 0;
}


上面的代码是当时直接写的，这道题主要考察的是单调降序子序列，当数组剩下的元素是单调递增时，即代表循环结束，
上面使用一个辅助数组来标记哪些元素已经被删除了，实际上后来思索后发现可以使用跳表来解决此问题，并且使用
跳表判断是否达到最后一个元素更加方便，且省去一些不必要的查询。
以下为例：
假设定义数组v[6];
则初始跳表为[1,2,3,4,5,-1] -1 代表到达表末
例如现在删除第3第4个元素，则跳表写为[1,2,5,4,5,-1],这样就跳过去了

发表于 2021-04-24 10:08:53 回复(0)
提交观点

问题信息

算法工程师 哔哩哔哩 2021
上传者：小小
难度：
7条回答 1611浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号