P3411 序列变换

· · 题解

P3411

主打的就是一个正难则反！

问最少的操作次数，其实就是最多的不操作次数。这样说可能有点怪，来个结论：

每个数至多操作一次（自证不难）。

所以本题等价于求最多几个数可以原地不动。显然，原地不动的数在最后序列变成有序的时候必然都是有序的，我们要做的是在原序列中提取一个有序的最长子序列。

好像是……板子？

戳啦，这个序列还有一个性质必须满足：是目标序列的子串。假设我们已经求出了这个合法的子序列，那么子序列的空隙里（不会有人不知道子序列可以是断断续续的吧）就是不能加入到子序列里做贡献的数，它们得被移开。而移开后，这个子序列就会凑到一起，变成目标序列的子串。

而这个子串有什么特点？那就是它们并非单纯的大于小于关系，而是对于一对相邻的数 a_{i-1},a_i（a_{i-1}<a_i），无法找到一个使得 a_i>a_j>a_{i-1} 的 j（这个就是很显然的排序的性质）。

于是我们可以开一个桶套 vector 存储对应值的下标，从小到大加入队列，过程中判断即可。

得到了最多的不操作次数，再结合上面的结论，答案显而易见。

Code:

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,a[N],l=1,r=1,ans,res,Max;
vector<int>v[N];
deque<int>d;
signed main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),v[a[i]].push_back(i),Max=max(Max,a[i]);
    for(int i=1;i<=Max;i++){
        for(int j=v[i].size()-1;j>=0;j--){
            int now=v[i][j];
            while(d.size()&&d.front()>now){//最大值在次大值前面
                while(d.size()&&a[d.back()]<a[d.front()])d.pop_back();//前面也失效了
                d.pop_front();
            }
            ans=max(ans,(int)d.size()+(int)v[i].size()-j);//目前合法序列长度
        }
        for(int j=0;j<v[i].size();j++)d.push_front(v[i][j]);
    }
    printf("%d\n",n-ans);
    // system("pause");
    return 0;
}

record