跳跃的排列

NC229194. 跳跃的排列

描述

小 $\text{B}$ 很喜欢排列，这次他有一个长为 ${n}$ 的排列 $a_1,a_2,\cdots,a_n$ 。由于他音游玩多了，所以他想让排列也跳跃起来。他定义一次排列的跳跃为：

令 $b_i$ 表示最大的 ${j}\ (i\le j\le n)$ 满足 $a_j\ge a_i$ ，则 $b_i=a_j$ 。最后对于所有 $i=1\sim n$ ，将 $a_i$ 赋值为 $b_i$ 。

他想重复上述操作若干次。若操作 ${k}$ 次和操作 ${k+1}$ 次序列保持不变，那么跳跃停止，跳跃次数为 ${k}$ 。

他想知道排列会跳跃多少次，请你来帮他计算一下。

大样例 https://uploadfiles.nowcoder.com/files/20211016/%E6%99%AE%E5%8F%8A%E7%BB%84-%E8%B7%B3%E8%B7%83%E7%9A%84%E6%8E%92%E5%88%97.zip

输入描述

第一行， 输入一个数 。
第二行输入  个数，第 i 个数表示 。

输出描述

输出排列的跳跃次数。

示例1

输入:

4
4 1 3 2

输出:

说明:

经过 1 轮操作后，序列变成 $\text{4 2 3 2}$ ，经过 2 轮操作后，序列仍然是 $\text{4 2 3 2}$ ，因此排列跳跃了 ${1}$ 次。

示例2

输入:

10
1 9 2 6 8 7 4 3 5 10

输出:

说明:

经过 1 轮操作后，所有数都变成了 $\text{10}$ ，经过 2 轮操作后，序列仍然全都是 $\text{10}$ ，因此排列跳跃了 ${1}$ 次。

示例3

输入:

8
8 7 6 5 4 3 2 1

输出:

说明:

经过 1 轮操作后，序列仍然是 $\text{8 7 6 5 4 3 2 1}$ ，因此排列没有进行跳跃。

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 242ms, 内存消耗: 420K, 提交时间: 2022-07-10 11:35:24

#include<bits/stdc++.h>
using namespace std;
int n,a,b;
int main()
{
	cin>>n>>a;
	for(int i=2;i<=n;i++)
	{
		int x;
		cin>>x;
		if(x>a)b=1;
		a=x;
	}
	cout<<b;
}

Pascal 解法, 执行用时: 99ms, 内存消耗: 588K, 提交时间: 2021-10-19 18:05:21

var
ans,num,n,i,p:longint;
begin
p:=0;
readln(n);
read(ans);
for i:=1 to n-1 do
begin
read(num);
if num>ans then p:=1;
ans:=num;
end;
writeln(p);
end.

Python3 解法, 执行用时: 338ms, 内存消耗: 123696K, 提交时间: 2022-07-10 13:47:45

n=int(input())
l1=list(map(int, input().split()))
a=min(l1)
if a==l1[-1]:
    print(0)
else:
    print(1)

上一题

下一题

详情