1.简化题意

给定数组

X

，其中的数都恰好出现

2

次。求相等的两数所在位置之间所包含的数的个数的最大值。

2.题目思路

2-1.绝对朴素的暴力

对于每个数，遍历一遍数组，找到与之相等的另一个数，并遍历它们之间的所有数，并计数，计算最大值。

2-2.相对朴素的暴力

上述方法代码相对复杂，且有许多优化的空间。

我们知道，设一个数所在的位置为

l

，另一个数所在的位置为

r

（这里，我们规定

l < r

），那么显然从

l

到

r

（包括

l

和

r

）共有

r - l + 1

个数，

l

和

r

之间（不包括

l

和

r

）有

r - l + 1 - 2 = r - l - 1

个数。

那么，我们可以把计数的复杂度由

\mathcal O(n)

变为

\mathcal O(1)

，即找到两个相等的数之后，直接套用上述公式计算，并取最大值。

时间复杂度为

\mathcal O(n^2)

，由于此题的

N \le 2000

，可以通过此题。

暴力代码

CPP

#include<iostream>
#include<cstdio>
using namespace std;
const int max_n=2002;
int n,x[max_n<<1],ans;
bool vis[max_n<<1];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=(n<<1);i++){
        scanf("%d",&x[i]);
    }
    for(int i=1;i<=(n<<1);i++){
        if(vis[i]){ //如果这个点已经被用过，那么跳过，避免重复计算
            continue;
        }
        vis[i]=true; //标记
        for(int j=1;j<=(n<<1);j++){
            if(vis[j]){
                continue;
            }
            if(x[j]==x[i]){ //如果两数相等，说明找到了相等的数
                vis[j]=true; //标记
                ans=max(ans,j-i-1); //计算最大值
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}

3.别急，还没结束

我们发现，上述暴力代码仍然有优化的空间。

也许有同学看到这里便不打算继续了，认为这里没什么用处，然而，这种类型的题目的

N

可以来到

10^6

左右，此时，题目依旧是可做的！

我们发现，上述代码的瓶颈在于：每次查找相等的数都需要重新遍历一遍数组。考虑如何优化这步操作。

我们可以用一个数组来记录每个数第一次出现的位置，~~众所周知~~当这个数第二次出现时，其位置一定在第一次出现位置的后面（废话），所以我们此时可以直接从数组中提取出位置并计算，更新答案。这样做就只需要遍历一次数组了！

时间复杂度为

\mathcal O(n)

。

本题作者用到的卡常小技巧

~~快读不再重复……~~

在本题中，数组

X

的长度为

2N

，在输入时，不知道大家是否这样写？

CPP

for(int i=1;i<=n*2;i++)

注意代码中的

\texttt{n*2}

，实际上，它可以转化为

\texttt{n<<1}

（其中

\texttt{<<1}

表示“二进制左移

1

位”），它可以省去一些时间。

虽然在本题中，这种写法并没有显著提高代码运行时间，但在算法竞赛中，这是常见的一种优化技巧。

4.代码-O(n)

注：代码仅供参考。

CPP

#include<iostream>
#include<cstdio>
using namespace std;
const int max_n=2002;
int n,x[max_n<<1],fl[max_n],ans; //fl[i]:数字   i 第一次出现的位置
bool aper[max_n];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=(n<<1);i++){ //n<<1 相当于 n*2，但 n<<1 的速度更快，所以经常用于竞赛中以减少程序用时
        scanf("%d",&x[i]);
        if(!aper[x[i]]){ //x[i] 从未出现过，标记，并记录当前位置
            aper[x[i]]=true;
            fl[x[i]]=i;
        }
        else{ //已经出现过一次，说明这是第二次出现，计算答案并取最大值
            ans=max(ans,i-fl[x[i]]-1);
        }
    }
    printf("%d\n",ans); //输出
    return 0;
}

题解：P13510 [KOI 2025 #1] 远方的卡片

文章操作