题解：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}

函数。首先我们统计原数组中每个数出现的次数，在统计有哪些数字出现了不止一次。然后枚举移动区间的左端点，并实时记录那些数字被删除了，那些数字又恢复了。总之就是枚举一个滑动的窗口，如果有一次所有的数字都最多只出现了一次，那就说明这个答案是可行的，具体详见代码。

代码

CPP

#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

的范围，都更新最短删除区间的长度就行啦！

代码

CPP

#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;	
}

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

文章操作

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

方法一

思路

实现

代码

方法二

思路

代码

相关推荐

评论

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