abc302G

崔化博 · 2023-05-23 22:27:52 · 题解

题目大意

给你一个序列，定义一次操作为交换任意两个元素，问最少几次操作使得序列变成单调不降，其中值域为 1~4

思路

我的思路有点奇怪。

一眼看去好像可以先把随便一个 1 先交换到最前面，其次是 2,3,4。然后看一下样例二是对的，然而样例一是错的。

样例一发现有两个 1 可以交换到第一个位置，然而我们随机选了一个，实际上是要把第二个 1 换过来，因为 3 正好换到单调不降后它应该在的位置，就节省了操作。

于是大致思路就出来了，对于每个位置，先优先找当前位置上的数应当在的位置范围内，如果有当前位置应当有的数的话，就优先换过来，否则我们默认换第一个。这个东西直接用一个 set 维护即可。

时间复杂度为 O(n \log n)，空间复杂度为 O(n)

我的代码可能实现的并不好，可以自己实现一下试试。

#include <bits/stdc++.h>
#define N 500005
#define ll long long
using namespace std;
int n,a[N],vis[N];
//这个函数表示找到值为zhi的数在排完序后应在的区间 
pair<int,int> zhao(int zhi) {
    int ans1=0,ans2=0;
    for(int i=1; i<=n; ++i) {
        if(a[i]==zhi) {
            ++ans2;
        }
        if(a[i]<zhi) {
            ++ans1;
        }
    }
    return make_pair(ans1+1,ans1+ans2);
}
priority_queue<int> s;
pair<int,int> chu[5];
signed main() {
    cin>>n;
    for(int i=1; i<=n; ++i) {
        cin>>a[i];
    }
    //提前预处理一下，方便O(1)查询 
    chu[1]=zhao(1);
    chu[2]=zhao(2);
    chu[3]=zhao(3);
    chu[4]=zhao(4);
    int lst=1,xian=0;//lst表示当前执行到了lst，xian是为了方便遍历 
    int ans=0;
    for(int qwq=1; qwq<=4; ++qwq) {//qwq表示当前已经排序到了值为qwq的数 
        xian=1;
        set<int> ying;
        for(int i=chu[qwq].second+1;i<=n;++i){
            if(a[i]==qwq)
                ying.insert(i);
            //找到应与当前区间换的数 
        }
        int lstt=lst;
        for(;xian<=chu[qwq].second-chu[qwq].first+1; ++lst,++xian) {//先优先找到换之后还能满足的 
            if(a[lst]==qwq)continue;
            auto it=ying.lower_bound(chu[a[lst]].first);
            bool flag=0;
            if(it==ying.end())//没找到 
                flag=1;
            if((*it)>chu[a[lst]].second)//没找到 
                flag=1;
            if(!flag){//交换并删除 
                swap(a[*it],a[lst]);
                ying.erase(it);
                vis[lst]=1;
            }
            ++ans;
        }
        for(lst=lstt,xian=1;xian<=chu[qwq].second-chu[qwq].first+1;++lst,++xian){//再次遍历当前区间，换之前没换的 
            if(a[lst]==qwq)continue;
            if(!vis[lst]){//没有被换过就换 
                swap(a[*ying.begin()],a[lst]);
                ying.erase(ying.begin());
                vis[lst]=1;
            }
        }
    }
    cout<<ans;
    return 0;
}