题解：CF2200D Portal

· · 题解

SOLUTION

闲话

令人赏心悦目的题目，一开始想复杂了（甚至还是错解）。

题目大意

给定一个长为 n 的排列 p，有 2 个门户，分别在 x 和 x+1 之间，以及 y 和 y+1 之间，可以进行以下操作：

  1. 将一个门户紧靠左侧元素移动到紧靠另一个门户右侧的位置。
  2. 将一个门户紧靠右侧元素移动到紧靠另一个门户左侧的位置。

求进行多次操作后，能得到的字典序最小的排列。

解题思路

我们注意到，两个门户之间的元素操作始终是在区间里面做循环位移，这个仔细推一下就会知道，而其余元素的顺序无法改变，那么我们很快得到贪心策略，现将两个门户区间内循环位移直到字典序最小，而其余元素由于顺序无法改变，我们可以看作门户区间在整个其他元素序列中进行游走，将其他元素序列进行从前往后遍历，直到有一个元素大于门户区间中的最小元素（即现在的第一个），将门户区间安插在当前遍历到的的前一个空位。

CODE

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int t , n , x , y , p[N];
void sol(){
    cin >> n >> x >> y;
    for(int i = 1;i <= n;i++)cin >> p[i];
    vector<int>ans;
    int id = 0;
    p[0] = 1e9;
    for(int i = x + 1;i <= y;i++){
        if(p[id] > p[i])id = i;
    }
    int pos = id;
    while(1){
        ans.push_back(p[pos]);
        if(pos == y)pos = x + 1;
        else pos++;
        if(pos == id)break;
    }
    for(int i = x + 1;i <= y;i++)p[i] = ans[i - x - 1];
    vector<int>tmp;
    vector<int>v , v2;
    for(int i = 1;i <= n;i++){
        if(i > x && i <= y)continue;
        tmp.push_back(p[i]);
    }
    bool flag = false;
    for(auto i : tmp){
        if(i > p[x + 1])flag = true;
        if(flag)v2.push_back(i);
        else v.push_back(i);
    }
    for(auto i : v)cout << i << ' ';
    for(int i = x + 1;i <= y;i++)cout << p[i] << ' ';
    for(auto i : v2)cout << i << ' ';
    cout << '\n';
}
int main(){
    cin >> t;
    while(t--)sol();
    return 0;
}