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;
}
标签:排列,cout,int,题解,元素,maxn,操作,P10155
From: https://blog.csdn.net/Zhou2010_/article/details/141334177