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

· · 题解

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;
}