51nod 1294 修改数组

题意：给出一个整数数组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;
}