P10155 题解

I_will_AKIOI · 2024-02-13 17:43:36 · 题解

当我看到出题人题解时，发现我的做法原来这么麻烦，看来我还是太菜了。

首先，n 肯定开始得放在第 n 个的位置上，否则当你选择 p_i=n 时，无法进行操作。

其次，我们需要将 i-1 插到 i 的前面。例如样例，开始你将 4 插到 5 的前面，肯定比将 3 插入好，因为你还需要再将 4 插到 5 的前面，浪费了一步。

然后考虑暴力。从 i=n-1 开始枚举，接着枚举排列 p，找到 p_j=i，将 p_j 插入到 p_i 前即可，复杂度 O(n^2)。

由于在数组中无法高效的完成插入操作，我们可以使用链表。每次操作时将 i 删除，然后插入到 i+1 的左边，如果 i 的右边刚好是 i=1，直接跳过，否则记录下操作的步数。

若你使用数组存链表，注意空间要开两倍，不然会爆。

#include<bits/stdc++.h>
using namespace std;
struct data{int val,l,r;}w[4000005];
int n,m,cnt,ans,a[2000005],in[4000005];
void insert_left(int x,int y)//在x的左边插入y
{
  int now=in[x];
  w[++cnt]=data{y,w[now].l,now};
  w[w[now].l].r=cnt;
  w[now].l=cnt;
  in[y]=cnt;
  return;
}
void insert_right(int x,int y)//在x的右边插入y
{
  int now=in[x];
  w[++cnt]=data{y,now,w[now].r};
  w[w[now].r].l=cnt;
  w[now].r=cnt;
  in[y]=cnt;
  return;
}
void erase(int x)//删除x
{
  int now=in[x];
  int le=w[now].l,ri=w[now].r;
  w[le].r=ri;
  w[ri].l=le;
  in[x]=0;
  return;
}
int main()
{
  ios::sync_with_stdio(0);
  cin>>n;
  for(int i=1;i<=n;i++)
  {
    cin>>a[i];
    insert_right(a[i-1],a[i]);//将a[i]插在a[i-1]的右边
    if(i==n&&a[i]!=n)//a[n]不是n，无解
    {
      cout<<-1;
      return 0;
    }
  }
  for(int i=n-1;i>=1;i--)
  {
    if(w[in[i]].r==in[i+1]) continue;//当前i的→边就是i+1，跳过
    erase(i);
    insert_left(i+1,i);
    //删除当前的数，再插入
    ans++;
  }
  cout<<ans;
  return 0;
}