A.「EZEC-10」排列排序
给你一个长度为 \(n\) 的排列 \(p_1,p_2, \cdots ,p_n\)。你需要把它排序。
每次可以花区间长度，即 \(r-l+1\) 的代价，选择排列中的任意一段区间 \([l,r]\)，并将 \([l,r]\) 从小到大排序。
现在你可以让他进行若干次这个操作，直到 \(p\) 中元素的值从 \(1\) 到 \(n\) 按升序排序，即对于 \(1\) 到 \(n\) 的每一个 \(i\)，都有 \(p_i=i\)。
求问花的代价最少为多少？
\(\operatorname{Solution:}\)
比赛时想了个加做法,两个指针从两边逼近,找到第一处 \(a[i]!=i\) 的,然后对中间这个大区间计算排序花费.但是容易找到反例
2 1 3 5 4,按上面的做法答案是 \(5\) ,但实际上只需要把 2 1 和 5 4 单独排序即可,花费为 \(4\) .
题解的方法是:
先让左指针尽量右移,然后让右指针从左指针的下一个位置开始,不断更新左右指针之间的最大值 \(maxv\) ,当右指针指到了 \(maxv\) 的下标位置时实施交换.
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#define endl '\n'
#define pb push_back
using namespace std;
typedef pair<int,int> PII;
const int N = 1e6+10;
int a[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin>>T;
while(T--)
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
int l = 1;
int res =0 ;
while(l<=n)
{
while(l<=n&&a[l]==l) l++;
if(l>n)break;
int r = l;
int maxv = a[l];
while(r<n&&r!=maxv){
r++;
maxv = max(maxv,a[r]);
}
res+=r-l+1;
l = r+1;
}
cout<<res<<endl;
}
return 0;
}