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

guoshengyu1231 · 2025-04-24 19:19:29 · 题解

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

方法一

思路

考虑到答案具备单调性，首先考虑二分答案。 \\ 那为什么这题能用二分答案呢？ \\ 首先我们要明白什么是二分答案？

其实通俗的讲，如果说暴力枚举是一个一个猜答案的话，那二分答案就是将答案用二分查找的方式找出来。 \\ 具体的，给定一个答案的范围，然后每次会算出这个范围的中间数 mid。接下来会有一个 \operatorname{check} 函数来检测猜到的 mid 是否满足题目要求，接着会根据实际情况适当修改值的范围。到最后只有一个数，就是最终的答案（其实就跟二分查找差不多，只不过查找的是答案）。

那这就不得不提到二分答案的使用条件了。 \\ 二分答案的使用需要同时满足以下几个核心条件： \\

解空间有序‌：问题的答案必须存在于一个有序的范围内（如数值区间），且存在明确的单调性特征。也就是：
- 当求解最大值时，若某个值 x 满足条件，则所有比 x 小的值也满足条件。
- 当求解最小值时，若某个值 x 满足条件，则所有比 x 大的值也满足条件。
例如，问题中出现“最大值最小化”或“最小值最大化”等双最值描述时，通常适用二分答案。
‌存在高效的判定函数：对于给定的候选答案 mid ，需要能在多项式时间（通常为 O(n) 或 O(n \log n)）内验证其是否满足题目要求。
‌判定逻辑独立于答案生成：判定函数的设计应仅依赖当前候选答案 mid，无需预先知道其他可能的解。这种独立性使得每次二分迭代只需关注当前 mid 的可行性。 \\

其实说了一大堆，都只是前置知识。 \\ 那么我们现在回到原题，首先看了看题目，发现满足二分答案的使用条件，所以可以使用二分答案。既然是二分答案，那么我们还是先考虑影响答案的因素吧。其实这个并不难，题目要求删除一个区间，使最终的序列最长且里面的数互不相同。那影响删除的区间的因素有区间的左右边界和区间的长度。但是他们三个中只需要确定两个就可以确定区间了。那我们该怎么选择呢？那接下来我们就要考虑那个条件是与答案有直接关系的，也就是他的优劣能确定答案的优劣，那显然是区间的长度，所以我们不妨二分删除区间的长度，在 \operatorname{check} 函数中枚举删除区间的左端点。

实现

代码的大致框架有了，接下来需要思考如何去实现这个算法。首先二分答案部分比较简单，我们可以先不管。重点是如何去实现 \operatorname{check} 函数。首先我们统计原数组中每个数出现的次数，在统计有哪些数字出现了不止一次。然后枚举移动区间的左端点，并实时记录那些数字被删除了，那些数字又恢复了。总之就是枚举一个滑动的窗口，如果有一次所有的数字都最多只出现了一次，那就说明这个答案是可行的，具体详见代码。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int n,a[maxn];
bool check(int x)
{
    int cnt[maxn],s=0;
    memset(cnt,0,sizeof cnt);
    for(int i=x+1;i<=n;i++)//覆盖了第一个区间，故从x+1开始计数 
     {
        cnt[a[i]]++;
        if(cnt[a[i]]==2) s++;
     }
    if(s==0) return true;
    for(int i=1;i+x<=n;i++)
     {
        cnt[a[i+x]]--;
        if(cnt[a[i+x]]==1) s--;
        cnt[a[i]]++;
        if(cnt[a[i]]==2) s++;
        //滑动窗口
        if(s==0) return true;
     }
    return false;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    int l=0,r=n;
    while(l<r)
     {
        int mid=l+r>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
     }
    cout<<n-l;
    return 0;
}

方法二

其实还有更简单且更高效的办法。

思路

我们可以从方法一的思想开始想，方法一，也就是二分答案，是通过二分区间长度来求解的。那我们可不可以根本不用枚举区间长度，或者说可以快速算出区间长度，然后直接枚举左端点求解。那既然是通过枚举左端点 l，那我们就得思考左端点为 l 和左端点为 l-1 和的答案有什么联系。显然，l 每扩大 1 的范围，就能够覆盖一个数，如果这个数被覆盖，那这个区间就可以再放出一个和这个数值相同的数，也就是右端点 r 可以缩小范围。在每次扩大 l 的范围，都更新最短删除区间的长度就行啦！

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int n,a[maxn],ans=1e9;
bool vis[maxn];//记录每个数字是否出现再原序列中（没被删除）
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    int l=1,r=n;
    while(l<=n&&!vis[a[l]]) vis[a[l++]]=true;
    while(r&&!vis[a[r]]) vis[a[r--]]=true;
    //初始化l,r
    while(l)
     {
        ans=min(ans,r-l+1);//更新答案
        vis[a[--l]]=false;//扩大左边界l
        while(r&&!vis[a[r]]) vis[a[r--]]=true;//缩小有边界r
     }
    cout<<n-ans;
    return 0;   
}