题目链接

题面：

题意：
给定一个全排列p，可以有两种操作：
（1）将倒数第二个数放到第一个。
（2）将第一个数放到最后一个。
对于操作（1），我们将连续的几次操作都视为一次操作。
问最少进行多少次操作（1）可以将 p 变为 1... n 1...n 1...n。

题解：
我们发现若干次连续的操作（2）会让序列进行循环，即只要变为相对顺序为 1... n 1...n 1...n然后进行操作（2）循环即可到达 1... n 1...n 1...n

我们发现若干次连续的操作（2）+ 若干次连续的操作（1）的作用其实就是将序列的任意一个数插入到任意一个位置。

问题转化为，我们将序列 p 看作一个环，然后从任意位置断开，求最长上升子序列的最大值。

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<set>
#include<list>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
#define lc (cnt<<1)
#define rc (cnt<<1|1)
//#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;
 
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const int mod=998244353;
const double eps=1e-1;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=1010;
const int maxp=1100;
const int maxm=4000100;
const int up=100000;
 
 
int a[maxn],b[maxn];
 
int main(void)
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]),a[i+n]=a[i];
    int maxx=0;
    for(int i=1;i<=n;i++)
    {
        int cnt=0;
        b[0]=0;
        for(int j=i;j<=i+n-1;j++)
        {
            if(a[j]>b[cnt]) b[++cnt]=a[j];
            else
            {
                int now=lower_bound(b+1,b+cnt+1,a[j])-b;
                b[now]=a[j];
            }
            maxx=max(maxx,cnt);
        }
    }
    printf("%d\n",n-maxx);
    return 0;
}