自动搬运

查看原文

来自洛谷，原作者为

	LSA AFO||ds和数数学不会

搬运于2025-08-24 23:01:47，当前版本为作者最后更新于2024-08-04 17:52:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Solution

考虑每操作一次对序列的大小关系会造成什么影响。

考虑相邻三个数 $x,y,z$。

若 $x<y<z$，对 $y$ 操作后仍然 $x<y<z$；

若 $x>y>z$，对 $y$ 操作后仍然 $x>y>z$；

若 $x>y<z$，对 $y$ 操作后则 $x<y>z$；

若 $x<y>z$，对 $y$ 操作后则 $x>y<z$。

证明代入 $y=x+z-y$ 即可。

为了方便，我们把小于号记作数字 $0$，大于号记作数字 $1$。

那么原序列我们可以根据大小关系转换成一个由 $01$ 构成的环（设原序列为 $\{a_n\}$ 转换后的序列为 $\{b_n\}$，则 $b_i=[a_i>a_{(i+1) \mod n}]$）。

比如样例第三个点 $0,5,9,7,3,1,6,4,8,2$ 就可以转换成 $0011101011$。

我们发现上面四种操作实质上对应着交换转换后环形序列的相邻两个数。

那么题意就转化为给定一个由 $01$ 构成的环，每次操作可以交换相邻两个数，求多少次操作能把所有的 $0$ 连在一起，所有的 $1$ 连在一起。

断环成链，那么就问题等价于求把一些 $1$ 移到最左边，一些 $1$ 移到最右边的最小操作次数最小值。

记序列的中点为 $mid$，我们把 $i \le mid$ 的 $1$ 移到左边，其他移到右边，我们发现一定存在一条边将它断开后形成的序列通过这种方式操作能得到最优的答案。

考虑如何实现，我们只需把转换后的数组复制一边在末尾，然后前缀和记录每 $1$ 的出现次数和下标和就能快速计算了。

时间复杂度 $O(n)$。

Code

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int> 
#define mk make_pair
#define fi first
#define se second
using namespace std;
ll read(){
    ll X = 0,r = 1;
    char ch = getchar();
    while(!isdigit(ch) && ch != '-') ch = getchar();
    if(ch == '-') r = -1,ch = getchar();
    while(isdigit(ch)) X = X*10+ch-'0',ch = getchar();
    return X*r;
}
const int N = 4e5+10;
int n,a[N],b[N];
ll cnt[N],sum[N];
int main(){
  int T = read();
  while(T--){
      n = read();
      for(int i=1;i<=n;i++) a[i] = read();
      a[n+1] = a[1];
      ll ans = 1e18;
      for(int i=1;i<=n;i++){
          if(a[i] < a[i+1]) b[i] = 0;
          else b[i] = 1;
      }
      for(int i=1;i<n;i++) b[i+n] = b[i];
      for(int i=1;i<2*n;i++)
          cnt[i] = cnt[i-1]+b[i],sum[i] = sum[i-1]+b[i]*i;
      int len = (n+1)/2;
      for(int i=1;i<=n;i++){
          ll sz1 = cnt[i+len-1]-cnt[i-1],sz2 = cnt[i+n-1]-cnt[i+len-1];
          ll ct1 = sum[i+len-1]-sum[i-1],ct2 = sum[i+n-1]-sum[i+len-1];
          sz1 = (i+i+sz1-1)*sz1/2; sz2 = (i+n-1-sz2+1+i+n-1)*sz2/2;
          ans = min(ans,ct1-sz1+sz2-ct2);
      }
      cout << ans << "\n";
    }
    return 0;
}