自动搬运

查看原文

来自洛谷，原作者为

	MspAInt **

搬运于2025-08-24 21:48:43，当前版本为作者最后更新于2023-07-02 22:15:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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