严格递增序列

 想了很久没想出来,无奈之下看了题解。

如果 a[i] < a[j] ,因为要保证都是整数,所以 j - i 必须要小于 a[j] - a[i] ,才能使区间 i,j 内的所有数均可修改。

j - i < a[j] - a[i] 移项得 a[i] - i < a[j] - j。

所以 a[i] 里要存 a[i] - i 的值,则求出最长不下降子序列后就可以保证其中的数都能够修改。

105 数据 n2 肯定跑不过,所以要用 n log n 的求法。

#include<bits/stdc++.h>
using namespace std;
int n,a[100001],h[100001],ans;
int main()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++)
    {
        scanf("%d",&a[i]);
        a[i] -= i;
    }
    int cnt=1;
    h[cnt] = a[1];
    for(int i = 2;i <= n;i ++)
    {
        if(a[i] > h[cnt]) h[++cnt]=a[i];
        else
        {
            int tmp=lower_bound(h + 1,h + 1 + cnt,a[i]) - a;//二分查找
            h[tmp]=a[i];
        }
    }
    cout<<n - cnt<<endl;
    return 0;
}

 

上一篇:CF704E. Iron Man


下一篇:SqlServer事务详解(事务隔离性和隔离级别详解)