题解归档 - cf220C

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf220C
• 本地来源：problems/cf220C/idea.md
• 题目链接：https://codeforces.com/contest/220/problem/C
• 原始标题：CF220C Little Elephant and Shifts

思路

CF220C Little Elephant and Shifts

题意

给定两个 1..n 的排列 a、b。排列距离定义为：存在相同数值 v，使 |pos_a(v) - pos_b(v)| 最小。

对 b 的每个循环移位（第 1 个为原序 b_1..b_n，第 k 个为 b_k..b_n b_1..b_{k-1}），求移位后与 a 的距离。输出 n 行。

做法

记 pos[x] 为 x 在 a 中的位置（1-indexed），f[i] = pos[b_i] - i。

第 s 个移位（0-indexed）时，原 b 中下标 i 的元素：

• 若 i ≥ s：新位置 i-s，贡献 |f[i]+s|
• 若 i < s：新位置 i-s+n，贡献 |f[i]+s-n|

注意边界 i=s 属于前半段（该元素旋到首位）。

答案为两类下标的最小值。

维护两个 multiset：

• S1：当前满足 i ≥ s 的 f[i]
• S2：当前满足 i < s 的 f[i]-n

对每个 s，在有序集上用 lower_bound(-s) 取相邻两个候选，可 O(log n) 求 min |x+s|。

每轮 s→s+1 时，将 f[s] 从 S1 移到 S2（插入 f[s]-n）。总复杂度 O(n log n)。

尝试记录

• 直接 O(n²) 公式对拍验证思路。
• 官方题解的双 set 懒偏移写法易写错；改为 multiset + lower_bound 更稳。

结论

AC 文件：solution.cpp。brute.cpp 为 O(n²) 暴力，用于对拍。

代码

来源：problems/cf220C/solution.cpp

/* Author: likely
 * Time: 2026-06-08 05:05:41
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=100005;
const ll inf=1e9;
ll n,i,j,k,p[maxn],a[maxn],b[maxn],f[maxn];
multiset<ll>s1,s2;
int main(){
    cin>>n;
    for(i=0;i<n;i++){
        cin>>a[i];
        p[a[i]]=i;
    }
    for(i=0;i<n;i++){
        cin>>b[i];
        f[i]=p[b[i]]-i;
        s1.insert(f[i]);
    }
    for(i=0;i<n;i++){
        ll ans=inf;
        auto it=s1.lower_bound(-i);
        if(it!=s1.end()) ans=min(ans,llabs(*it+i));
        if(it!=s1.begin()){
            --it;
            ans=min(ans,llabs(*it+i));
        }
        it=s2.lower_bound(-i);
        if(it!=s2.end()) ans=min(ans,llabs(*it+i));
        if(it!=s2.begin()){
            --it;
            ans=min(ans,llabs(*it+i));
        }
        cout<<ans<<"\n";
        if(i<n-1){
            it=s1.find(f[i]);
            if(it!=s1.end()) s1.erase(it);
            s2.insert(f[i]-n);
        }
    }
    return 0;
}