题解：CF2200D Portal

OLink · 2026-05-02 14:51:03 · 题解

给你一个长度为 n 的排列 p 和两个传送门位置 x 和 y，然后你可以无限操作使字典序最小。

考虑简化操作：

对于 [3,\mathbf{\color{red}{\mathcal{O}}},4,2,\mathbf{\color{red}{\mathcal{O}}},1]：

1. 第 1 部分 [\mathbf{\color{red}{\mathcal{O}}},4,2,\mathbf{\color{red}{\mathcal{O}}}]（也就是内部），其实就是内部循环。
2. 第 2 部分 [3,\mathbf{\color{red}{\mathcal{O}}}] 和 [\mathbf{\color{red}{\mathcal{O}}},1]（外部，由前后半部分组成），通过“穿梭”在前后来往。

因为，1,2 部分无法互相影响，于是我们可以把它分成两个部分，内部和外部。

考虑如何最优：

1. 对于内部，模拟循环交换使字典序最小。
2. 对于外部，只要前半部分都小于内部的第一个值就可以了（这里内部已为字典序最小）。

:::success[AC code 具体实现看代码]

#include<bits/stdc++.h>
#define endl '\n'
#define pb push_back
using namespace std;
using ll=long long;
#define to(i,o,p) for(ll i=o;i<=p;++i)
const int N=2E5+10;
ll n,x,y,p[N],Min=inf,it;
bool is;
deque<ll>mid;
queue<ll>other;
void solve(){
    //初始化
    while(!other.empty())other.pop();
    while(!mid.empty())mid.pop_front();
    Min=inf;

    cin>>n>>x>>y;
    to(i,1,n)cin>>p[i];
    to(i,x+1,y){
        mid.pb(p[i]);
        Min=min(Min,p[i]);//Min为最小值
    }
    it=-1;//外部前半部分最后面的数
    is=true;
    to(i,1,n){//外部前半部分必须小于Min(内部的第一个值)
        if(x+1<=i&&i<=y)continue;
        other.push(p[i]);
        if(is&&p[i]<Min)it=p[i];
        else is=false;
    }

    while(!mid.empty()&&mid.front()!=Min){//内部循环
        mid.pb(mid.front());
        mid.pop_front();
    }
    if(it!=-1){//是否有前半部分
        while(!other.empty()&&other.front()!=it){//前半部分
            cout<<other.front()<<" ";
            other.pop();
        }
        cout<<other.front()<<" ";other.pop();
    }

    for(ll x:mid)cout<<x<<" ";//内部

    while(!other.empty()){//后半部分
        cout<<other.front()<<" ";
        other.pop();
    }
    cout<<endl;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int T;
    cin>>T;
    while(T--)solve();
    return 0;
}

::::