1 题意

给定一个排列 p p p,每次可以选择一个数 p i p_i pi,将它插入到它之后的第一个大于它的数之前,最小化使整个排列单调不降的次数,若无法做到,输出 -1

2 分析

先说无解的情况,如果排列中最大的元素不在最后一个,那么最大的元素之后没有比它大的元素,就无法进行操作,故无解。

在有解的情况下,考虑贪心思路,从倒数第二大的元素开始操作,若该元素之后没有比它小的元素,就不进行操作,若有比它小的元素,就进行操作,因为该元素是为进行操作的元素中最大的,所以会将它插入到所有未进行操作的元素的后面,从而保证排列的有序性。

3 代码

#include<bits/stdc++.h>
using namespace std;
int n,a[2000005],b[2000005],maxn,ans;
int main()
{
   
  cin>>n;
  for(int i=0;i<n;i++)
  {
   
    cin>>a[i];
    maxn=max(maxn,a[i]);//求排列中的最大值
  }
  if(a[n-1]!=maxn)//判断无解
  {
   
    cout<<-1;
    return 0;
  }
  b[n-1]=INT_MAX;
  for(int i=n-2;i>=0;i--)
  {
   
    b[i]=min(b[i+1],a[i+1]);//求该元素之后的所有元素中的最小值
    if(a[i]>b[i])ans++;//判断是否进行操作
  }
  cout<<ans;
  return 0;
}