每日一题之混乱的草稿纸

问题描述

一年一度的蓝桥杯省赛即将开赛，小蓝卧薪尝胆，目标直指省一。

为了实现这个宏伟目标，小蓝偷偷准备了一份 NN 行的代码模板，分别写在 NN 张草稿纸上（每张草稿纸上都写有一行代码，并用 11 到 NN 的数字标记了每一行代码的行号）然后偷偷带入了考场（没错，小蓝作弊了）。

然而，命运弄人！当小蓝从口袋里掏出草稿纸时，竟发现草稿纸的顺序全乱了（毫无规律地堆叠在一起，例如，最顶端可能是行号为 77 的草稿纸，其下依次是行号为 99 、行号为 22 的草稿纸）。

为了不被监考老师发现，小蓝决定进行如下操作：

• 将任意一张草稿纸抽出来，放到最上面。

请问，小蓝最少需要多少次这样的操作，才能将代码按照行号 11 到 NN 从上往下的顺序排列好呢？

输入格式

第一行输入一个整数 NN（1≤N≤2×1051≤N≤2×105），表示草稿纸的数量，也就是代码的行数。

接下来一行包含 NN 个整数，以空格隔开，依次表示混乱堆叠的草稿纸从上往下的行号排列情况。

输出格式

输出一个整数，表示小蓝的最少操作次数。

#include <iostream>
#include<vector>
typedef long long ll; 
using namespace std;int main()
{// 请在此输入您的代码ll n;cin>>n;vector<ll> a(n);for(auto &x:a){cin>>x;}int ans=n;for(int i=n-1;i>=0;i--){if(a[i]==ans)ans--;}cout<<ans;return 0;
}

这道题与喜糖摆放那道题有点相似，但思路不太一样，同样都是找不需要移动的数字，只不过一个是去找升序，一个是找降序。问题里提到一个很关键的点，就是给出的数字一定是1~N的等差数列。我们可以利用这个特性，去找一个递减序列，直到找不到递减1的数，那么找到的这个递减序列就不需要移动。