题解：P7015 [CERC2013] Crane

Lemansky · 2024-08-08 13:47:55 · 题解

题意

翻译其实蛮清楚了，每次选择一段区间，将其前半部分与后半部分直接交换，从而把序列从小到大排序。构造一个操作序列即可。

这里补充一下原题面的点：序列是个 1 到 n 的排列。

思路

对于每组数据：

• 考虑一种贪心的暴力操作方法：把 1 到 n 从小到大依次归位（a_i=i），其合理性在于后面对右边数的操作不会影响左边已归位的数。

• 如果当前把 i 归位，尽可能优的方法是选区间 [i,pos_i]，pos_i 是 i 当前的位置，这样每次就能向终点前进大约一半。

• 举个例子，序列是 \{4,3,2,1\}，先操作 [1,4] 变为 \{2,1,4,3\}，再操作 [1,2] 变为 \{1,2,4,3\}。这样 1 就归位了，恰好 2 也归位，再操作 [3,4] 即可。

• 但是注意操作序列中的区间长度必须是偶数，因此需要微调区间的选择（即 [i+1,pos_i]）。

具体可以见代码。

复杂度和操作分析

对于每组数据：

• 注意到每次归位一个数大约需要 \log n 次操作（每次归一半），因此估计最坏也就 n\log n 次操作，n\le 10^4 对于题目的限制来说完全够用了。

• 至于时间复杂度，SPJ 能跑过去那我们肯定可以每次归位最多产生 n 次单位交换，暴力最坏是 O(n^2) 的复杂度，但其实远远到不了，直接操作就过了。

注意本题的多测限制。

Code

#include<bits/stdc++.h>
using namespace std;
int t,n,m,a[10005],b[10005];//b数组存位置
int s,l[114514],r[114514];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n,m=1,s=0;
        for(int i=1;i<=n;++i) cin>>a[i],b[a[i]]=i;
        while(1){
            while(b[m]==m) ++m;
            if(m>n) break;
            while(b[m]!=m){//还没归位
                ++s,l[s]=m+(b[m]-m+1)%2,r[s]=b[m];
                int w=(l[s]+r[s])/2;
                for(int i=l[s];i<=w;++i){
                    swap(a[i],a[i+w-l[s]+1]);
                    swap(b[a[i]],b[a[i+w-l[s]+1]]);
                }
            }
        }
        cout<<s<<'\n';
        for(int i=1;i<=s;++i) cout<<l[i]<<' '<<r[i]<<'\n';
    }
    return 0;
}