P10843 【MX-J2-T4】Turtle and Cycles 题解

解题思路

首先，观察操作的本质。设 $x = a_{(i-1) \bmod n}$, $y = a_i$, $z = a_{(i+1) \bmod n}$，那么操作将 $a_i$ 变为 $x + z - y$。考虑差分数组，定义 $b_i = a_i - a_{i-1}$（环形处理，$a_{-1} = a_{n-1}$）。操作前，$b_i = y - x$, $b_{i+1} = z - y$；操作后，$b_i' = (x+z-y) - x = z - y = b_{i+1}$, $b_{i+1}' = z - (x+z-y) = y - x = b_i$。因此，一次操作相当于交换了相邻的差分值 $b_i$ 和 $b_{i+1}$。

一个位置 $i$ 是好的当且仅当 $a_{i-1} < a_i$ 且 $a_{i+1} < a_i$。在差分数组上，这等价于 $b_i > 0$ 且 $b_{i+1} < 0$。定义二进制序列 $s_i = 1$ 如果 $b_i > 0$，否则 $s_i = 0$。那么好位置对应 $s_i = 1$ 且 $s_{i+1} = 0$ 的位置。

序列是好的当且仅当恰好有一个好位置，即在环形序列中恰好有一个 $s_i = 1$ 且 $s_{i+1} = 0$ 的位置。这在环形二进制序列中意味着所有 $1$ 是连续的，所有 $0$ 是连续的（即序列形如 $111\ldots000$ 或 $000\ldots111$，但根据差分条件，需要的是 $1$ 到 $0$ 的变化点）。

通过操作交换相邻差分值，我们可以重新排列差分数组。问题转化为：通过相邻交换，将二进制序列 $s$ 排列成所有 $1$ 连续的形式（即连续 $1$ 后接连续 $0$），所需的最小交换次数。

最小交换次数的计算等价于将所有的 $1$ 移动到连续位置所需的最小移动步数。设 $1$ 的个数为 $k$，$1$ 的位置为 $q_1, q_2, \ldots, q_k$（排序后）。目标是将这些 $1$ 移动到连续位置 $L, L+1, \ldots, L+k-1$。最小交换次数为 $\min_L \sum_{j=1}^k |q_j - (L+j-1)|$。

在环形序列中，需要处理环的循环特性。一个常见技巧是将序列复制一份，然后计算线性序列上的最小代价。

算法实现

根据排列 $a$ 计算差分值 $b_i = a_i - a_{i-1}$，并生成二进制序列 $s_i = [b_i > 0]$。

将 $s$ 复制一份得到长度为 $2n$ 的序列，以便处理环形。

设 $f[i]$ 表示 $s[1..i]$ 中 $1$ 的个数。

$g[i]$ 表示 $s[1..i]$ 中 $1$ 的索引加权和（即 $\sum_{j=1}^i j \cdot s_j$）。

$sg[i]$ 表示 $s[i..2n]$ 中 $1$ 的逆序索引加权和（逆序索引为 $2n-j+1$）。

计算最小代价：对于每个可能的起始位置 $i$（$1 \leq i \leq n$），将环形序列视为从 $i$ 开始的长度为 $n$ 的段，计算将 $1$ 移动到该段前半部分和后半部分的代价：

左半部分$[i, \text{mid}]:\\$ 代价：$lres = g[mid] - g[i-1] - lk * i - (lk-1)*lk/2$

右半部分$[\text{mid}+1, i+n-1]:\\$ 代价：$rres = sg[mid+1] - sg[i+n] - rk * (2*n - (i+n-1) + 1) - (rk-1)*rk/2$

总代价为 $lres + rres$，取最小值。

复杂度分析 时间复杂度：$O(\Sigma n)$

空间复杂度：$O(n)$

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=4e5+5;
int t, n, a[N];
ll g[N],f[N],sg[N];
bool b[N];
ll cal(int n){
    ll ans=1e18;
    for(int i=1; i<=n; i++) {
        int mid=i+n/2-1;
        ll lk=f[mid]-f[i-1];
        ll lres=g[mid]-g[i-1]-lk*i-(lk-1)*lk/2;
        ll rk=f[i+n-1]-f[mid];
        ll rres=sg[mid+1]-sg[i+n]-rk*(2*n-(i+n-1)+1)-(rk-1)*rk/2;
        ans = min(ans,lres+rres);
    }
    return ans;
}

void solve() {
    cin>>n;
    for(int i=1; i<=n; i++) {
		cin>>a[i];
        a[i+n]=a[i];
    }
    for(int i=2; i<=n+1; i++) {
        b[i-1]=(a[i]>a[i-1]);
        b[i-1+n]=b[i-1];
    }
    int tot = 2*n;
    for(int i=1; i<=tot; i++) {
        f[i]=f[i-1]+b[i];
        g[i]=g[i-1]+i*b[i];
    }
    sg[tot+1]=0;
    for(int i=tot,j=1; i>=1; i--,j++) {
        sg[i]=sg[i+1]+j*b[i];
    }
    cout<<cal(n)<<'\n';
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>t;
    while(t--) solve();
    return 0;
}

（这是本蒟蒻的第一篇题解，不喜勿喷，QAQ）

标题

思路

解题方法

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code