严格递增序列

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

如果 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 的值，则求出最长不下降子序列后就可以保证其中的数都能够修改。

10⁵ 数据 n² 肯定跑不过，所以要用 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;
}