CF1257C Dominated Subarray


题意简述:

给定一个序列 找出其中最短的连续子段使得子段中只有一个众数(子段长度大于等于2)

题解:

首先考虑一下假如有一段连续相同的数字 那么答案就一定是2 即从连续的一段中随便挑连续的两个 那么众数就是这个数 那么接下来只剩下没有连续相同数字的情况

那么我们可以考虑一下答案是怎么构成的 因为是最短 所以肯定是首位两个的数字相同 中间是其他的数字 那么我们就可以扫一遍数组 每次对于数字相同的相邻的两个位置做差取最小值 那么就肯定可以得到答案了

AC代码:

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#include<set>
using namespace std;
template<class T>inline void read(T &x) {
    x=0; int ch=getchar(),f=0;
    while(ch<'0'||ch>'9'){if (ch=='-') f=1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    if(f)x=-x;
}
const int inf=0x3f3f3f3f;
const int maxn=200050;
int T,n;
int a[maxn];
int last[maxn];
int main()
{
    cin>>T;
    while(T--)
    {

        read(n);
        for(int i=1;i<=n;i++) read(a[i]);
        for(int i=0;i<=n;i++) last[i]=0;
        if(n==1) puts("-1");
        else
        {
            int ans=inf;
            for(int i=1;i<=n;i++)
            {
                if(last[a[i]]!=0)
                {
                    ans=min(ans,i-last[a[i]]+1);
                }
                last[a[i]]=i;
            }
            if(ans==inf) puts("-1");
            else cout<<ans<<endl;
        }
    }
    return 0;
}

文章作者: songhn
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 songhn !
评论
 上一篇
CF1239A Ivan the Fool and the Probability Theory CF1239A Ivan the Fool and the Probability Theory
题意简述:给定一个 $n\cdot m$ 的方格图,每个格子可以被染成黑色或白色,且与其相邻的四个格子中至多只有一个与其颜色相同,求方案数。 题解:我们可以一行一行的考虑 首先假如第一行存在连续的两个1 那么后面的状态就全部可以推出 因为
2019-11-15
下一篇 
tyvj1340 送礼物 tyvj1340 送礼物
题意简述:有$n$个物品和一个容量为$w$的背包 求出背包最多能装多大体积的物品($w\leq 2^{31}-1$,$n\leq 45$) 题解:该题是经典的超大背包问题 对于这样这样$n$很小$v$很大的背包问题我们可以考虑搜索 假如直
2019-11-12
  目录