CF1907F

DDF_ · 2025-09-16 20:42:27 · 题解

题意

给一个数组，可以将其进行两种操作：翻转，循环右移一位。求最小操作数使得它单调不减。

题面

好的样例创造好的题目，样例使我在打这题时思路特别的顺畅。

首先，发现两种操作都不会影响两个元素的相对位置（相邻的位置仍然相邻，相距 2 的位置仍然相距 2）。可以得出翻转不会超过 2 次。

发现右移后翻转，等于翻转后的串左移。所以“右移 n 次，翻转，右移”的操作序列不优。

因此发现以下四种操作方案可能会最优：“翻转，右移 x 次，翻转”（即为“左移 x 次”），“右移 x 次”，“翻转，右移 x 次”或“右移 x 次，翻转”。

由于环形右移，所以使用常有的套路：将整个序列复制一遍接到后面。

如果发现接后的序列单调不升/不降的最长子串长度小于 n，则无解。

如果发现大于 n，那么这个值一定为 2\times n，也就是全部元素相等的情况，输出 0。

如果最长单调不降子串长度等于 n，上述的前两种方案可用，从 n 到 2 \times n 枚举求解；单调不升的情况同理（后两个方案可用）。

具体地，对于每个位置 i，形成子串 [i-n+1,i]，可以 O(1) 求要从原序列到此处需要循环移动几次。从 n 开始，i 每往右枚举一步，就把第一位移到最后一位，然后其余往左移一位，因此在第 i 位左移了 i-n 位。同理，i 从 2 \times n 开始，每往左一步便是循环右移一步，因此在第 i 位右移了 2 \times n -i 位。

时间复杂度 O(n)。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=4e5+5;
int _;
int n;
int a[N],cnt1[N],cnt2[N],r1,r2;
int ans1,ans2;
void solve() {
    scanf("%d",&n),r1=r2=0,ans1=ans2=N;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) a[i+n]=a[i];
    for(int i=1;i<=2*n;i++) {
        if(a[i]>a[i-1]) cnt1[i]=cnt1[i-1]+1,cnt2[i]=1;
        if(a[i]<a[i-1]) cnt2[i]=cnt2[i-1]+1,cnt1[i]=1;
        if(a[i]==a[i-1]) cnt1[i]=cnt1[i-1]+1,cnt2[i]=cnt2[i-1]+1;
        r1=max(r1,cnt1[i]),r2=max(r2,cnt2[i]);
    }
    if(r1<n&&r2<n) return puts("-1"),void();
    if(r1>n&&r2>n) return puts("0"),void();
    if(r1==n) for(int i=n;i<=2*n;i++) if(cnt1[i]==n) ans1=min(ans1,min(2*n-i,i-n+2));
    if(r2==n) for(int i=n;i<=2*n;i++) if(cnt2[i]==n) ans2=min(ans2,min(2*n-i,i-n)+1);
    printf("%d\n",min(ans1,ans2));
    return;
}
int main() {
    scanf("%d",&_);
    while(_--) solve();
    return 0;
}