CF1907F

题意

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

题面

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

首先，发现两种操作都不会影响两个元素的相对位置（相邻的位置仍然相邻，相距

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)

。

代码

CPP

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

文章操作

题意

题面

代码

相关推荐

评论

CF1907F