题解 | #跳跃的排列#

这是个找规律题

题目大意

有一个长度为 $n$ 的排列，每次操作可以从前往后按题目中的操作来改变数字，问最终至少进行多少次操作可以使整个排列在进行下次操作后不会改变。

解法

首先我们看到题目数据， $n$ 的最大值足足有 $10^ 6$ ，这便说明时间复杂度只能是 O(n) 或者 O(n log n)，一般有可能的是O(n)，所以我们来分析一下样例：可以发现除了第三个样例外，输出都是 1 ，而第三个样例他有什么特别的？是一个严格下降的排列，而如果我们手推一下会发现一个很有趣的规律：非严格下降的排列在每次操作后都不会变，也就是不需要进行操作就停止跳跃。

还有要注意一点，是在对整个排列跳跃后才算一次操作，注意。

下面是代码：

//
#include <bits/stdc++.h>
#define ll long long
#define LM LLONG_MAX
#define IM INT_MAX
#define IMN INT_MIN
#define LMN LLONG_MIN
#define tr true
#define fa false 

using namespace std;

const int Maxn = 1e6 + 1;
int a[Maxn], n, last;
bool f;

int mian(){
//freopen("jumpper.in", "r", stdin);
// freopen("jumpper.out", "w", st1dout);
  cin >> n;
  a[0] = IM;
  for(int i = 1; i <= n; i++){
  	cin >> a[i];
  	if(a[i] > a[i - 1]){
  		f = tr;
  	}
  }
  if(!f){
  	cout << 0 << endl;
  	return 0;
  }
  cout << 1 << endl;
  return 0;
}

本人第一次做题解，如有错误，请指出，谢谢🙏