Codeforces 1257C Dominated Subarray 题解

博客观赏效果更佳

题意简述

定义“支配数组”：长度>=2，且出现次数最多的那个数字唯一。

给定一个数组，请你求出这个数组中，长度最小的是“支配数组”的连续子序列的长度。

数组长度<=2e5。

思路

最短的“支配连续子序列”，显然是：最左边和最右边两个数字相同，中间的数组两两不同。

设pre[i]表示a中上一个和a[i]的值相同的位置。换句话说，pre[i]=max{j，满足a[j]==a[i]}

那么只要求所有i-pre[i]+1的最小值即可。

代码

#include 
using namespace std;
namespace Flandre_Scarlet
{#define N 255555#define F(i,l,r) for(int i=l;i<=r;++i)#define D(i,r,l) for(int i=r;i>=l;--i)#define Fs(i,l,r,c) for(int i=l;i<=r;c)#define Ds(i,r,l,c) for(int i=r;i>=l;c)#define MEM(x,a) memset(x,a,sizeof(x))#define FK(x) MEM(x,0)#define Tra(i,u) for(int i=G.Start(u),__v=G.To(i);~i;i=G.Next(i),__v=G.To(i))#define p_b push_back#define sz(a) ((int)a.size())#define iter(a,p) (a.begin()+p)void R1(int &x){x=0;char c=getchar();int f=1;while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();x=(f==1)?x:-x;}void Rd(int cnt,...){va_list args;va_start(args,cnt);F(i,1,cnt) {int* x=va_arg(args,int*);R1(*x);}va_end(args);}int n,a[N];void Input(){R1(n);F(i,1,n) R1(a[i]);}int pre[N],pos[N];void Soviet(){MEM(pos,-1);MEM(pre,-1);bool flag=0;int ans=0x3f3f3f3f;F(i,1,n){pre[a[i]]=pos[a[i]];pos[a[i]]=i;if (pre[a[i]]!=-1) ans=min(ans,i-pre[a[i]]+1),flag=1;}if (!flag) puts("-1");else printf("%d\n",ans);}#define Flan voidFlan IsMyWife(){int t;R1(t);F(i,1,t){Input();Soviet();}}
}
int main()
{Flandre_Scarlet::IsMyWife();getchar();getchar();return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！