Mayflyyh
Mayflyyh
MayFlyyh's Blog
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;
}
本文链接:http://www.mayflyyh.com/archives/417
知识共享许可协议
本文采用CC BY-NC-SA 3.0进行许可。
首页      DP      51nod 1294 修改数组
http://0.gravatar.com/avatar/6cc3a2831375e487976e09c80dfcb52e?s=256&d=monsterid&r=g

MayFlyyh

文章作者

Oier

发表评论

textsms
account_circle
email

MayFlyyh's Blog

51nod 1294 修改数组
题意:给出一个整数数组A,你可以将任何一个数修改为任意一个正整数,最终使得整个数组是严格递增的且均为正整数。问最少需要修改几个数? n<=100000,0<=a[i]<=10^9 因…
扫描二维码继续阅读
2018-10-23