官方题解｜海贼宝藏密码

题目大意

为你在一个序列中挖空， 能否根据 严格递增 这个特性来还原原序列。求挖空之后剩余序列长度的最小值。

解题思路

很容易想到一点就是，挖的空越长，剩余的数字越少。怎么求挖空的最大值呢？ 首先我们找到一个最长的连续序列满足相邻的数字相差1 ， 那么除开两头，我们中间都可以挖空，此时剩下的数字最少。但是注意样例 2 的情况有点特殊，其实这种情况相当于在序列前面塞了一个 $0$ 。同理序列的后面也要加上个 $1001$ 此时就可以跑出正确答案了。

参考代码

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
int a[1005];
int main(){
	int n;
	cin>>n;
	a[1]=0;//前面塞个0
	a[n+2]=1001; //后面塞个1001
	for(int i=2;i<=n+1;i++)cin>>a[i];
	int cnt=1;
	int maxx=0;
	for(int i=2;i<=n+2;i++){
		if(a[i]==a[i-1]+1){//找到最长的相邻数差为1的序列
			cnt++;
		}
		else cnt=1;
		maxx=max(maxx,cnt);
	} 
	cout<<n-max(0,maxx-2)<<endl;
	return 0;
}