题解：P12280 [蓝桥杯 2024 国 Python A] 特别的数组

cyntmeay · 2025-11-21 10:49:46 · 题解

题目大意

题面已经说明清楚不做补充。

思路启发

如果我们知道特别的数组的长度最大是多少哪么我们就可以通过构造判断可不可以是这个最大值，所以这个题我们可以想到二分答案。

思路

• 先二分出最大值。
• 在判断函数中，因为 a_i \le 10^5，所以可以直接用一个桶数组来存储 a_i 出现的次数，接下来在 a_x+1 到 a_n 这几个数如果总的出现次数为 2，那就将其用一个变量存储下来（之后要用，这里用 cnt）。
• 特殊情况：如果 cnt=0，说明二分到的答案大了需要变小，返回 1。
• 我们从 1 枚举到 n-x，这里被我分成了两个步骤，第一个是增加 a_i 的出现次数，如果次数这时候为 2 那么 cnt 就加上 1；另外一种是减少 a_i+x 的出现次数，如果在操作后 x+a_i=1 了，那么 cnt 就要减 1。
• 如果在枚举循环的过程中 cnt=0 了说明二分到的答案大了需要变小，返回 1。如果到循环结束 cnt 也不是 0 那么说明答案小了需要变大。

关键代码

bool check(int x){//判断函数 
    int t[100005];//桶数组 
    int cnt=0;
    for(int i=1;i<=100000;i++){
        t[i]=0;//初始值 
    }
    for(int i=x+1; i<=n; i++){//统计a[i]有多少个以及计算cnt 
        t[a[i]]++;
        if(t[a[i]]==2){
            cnt++;
        }
    }
    if(cnt==0){//特殊情况 
        return 1;
    }
    for(int i=1; i+x<=n; i++){
        t[a[i+x]]--;//第二种情况：减少 
        if(t[a[i+x]]==1){
            cnt--;
        }
        t[a[i]]++;//第一种情况：增加 
        if(t[a[i]]==2){
            cnt++;
        }
        if(cnt==0){//答案大了 
            return 1;
         }
    }
    return 0;//答案小了 
}