题意:给出一个整数数组A,你可以将任何一个数修改为任意一个正整数,最终使得整个数组是严格递增的且均为正整数。问最少需要修改几个数?
n<=100000,0<=a[i]<=10^9
因为新生成的数列必须是正整数,那么第一个数必至少为1,同样,每个数在新生成的数列中至少应该为下标。。
那么除去那些值小于自身下标的,剩下的数从取值方面没问题,但有可能不递增,所以我们保留一个最长不下降子序列就可以了。
首先,最长不下降子序列的值显然满足条件,我们思考那些刚才被除去的值为什么可以插进来。
b[i]=a[i]-i
b[j]=a[j]-j
i+x<j
b[i]<=b[j]
a[i]-i<=a[j]-j
j-i<=a[j]-a[i]
j-i>x
显然,如果b[i]和b[j]属于这个最长不下降子序列,那么中间必是有一个值可以被添加的。(如果下标间隔为x,那中间就一定可以放x个值)
#include<bits/stdc++.h>
const int N = 101000;
int a[N],b[N],n,ans,t,m;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]),b[i]=a[i]-i;
for(int i=1;i<=n;++i)
if(b[i]>=0) a[++m]=b[i];
if(!m) ans=n;
else{
b[t=1]=a[1];
for(int i=2;i<=m;++i){
if(a[i]>=b[t]){
b[++t]=a[i];
}
else{
int s=std::upper_bound(b+1,b+1+t,a[i])-b;
b[s]=a[i];
}
}
ans=n-t;
}
printf("%d\n",ans);
return 0;
}
0 条评论