递增

一道最长上升子序列的模板题（就是双倍经验的题），这里还是从头来好好讲一遍吧。。。

题目描述

现有数列A_1,A_2,cdots,A_NA1​,A2​,⋯,AN​，修改最少的数字，使得数列严格单调递增。

输入输出格式

输入格式：

第1 行，1 个整数N

第2 行，N 个整数A_1,A_2,cdots,A_NA1​,A2​,⋯,AN​

输出格式：

1 个整数，表示最少修改的数字

输入输出样例

输入样例#1： 复制

3
1 3 2

输出样例#1： 复制

1

说明

• 对于50% 的数据，N le 10^3N≤103

• 对于100% 的数据，1 le N le 10^5 , 1 le A_i le 10^91≤N≤105,1≤Ai​≤109

对于这道题，显然：如果要改动最小，那么只要改掉除了最长上升子序列以外的数就行了，答案就是总长-最长上升子序列长度。

什么是最长上升子序列？

简单来说，最长上升子序列就是求一个序列中最长的连续上升的字串长度，题目说的是严格递增，但是数据大于和大于等于都过了。。。强烈要求加强数据qaq

一看数据范围，显然n^2一定会超时，那么考虑一种nlogn的做法

我们设low[i]表示序列长度为i最小的结尾元素是多大。

那么我们从头开始扫，对于每一个数，只有两种情况：（对于这道题）

1.大于目前low数组的最后一个元素，那么显然我们应该将它加入到low数组中，数组长度加1

2.小于等于，那么这个元素也不是一无是处，我们就用它来更新low数组的值，我们找到第一个比他大的数，那么长度为该数下标的最长上升子序列末尾的最小值就是这个新元素啦！

有人可能还是会说：

你这个在极端数据面前还是n^2啊。。。

我说：

你会二分查找吗？。。。

最后，附上本题代码：

#include<cstdio>
using namespace std;
int a[100005],low[100005],ans;
int dfs(int*a,int r,int x)
{
    int l=1,mid;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(a[mid]<=x)
        {
            l=mid+1;
        }
        else
        {
            r=mid-1;
        }
    }
    return l;
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&a[i]);
    }
    low[1]=a[1];
    ans=1;
    for(int i=2; i<=n; i++)
    {
        if(a[i]>low[ans])
        {
            low[++ans]=a[i];
        }
        else
        {
            low[dfs(low,ans,a[i])]=a[i];
        }
    }
    printf("%d",n-ans);
    return 0;
}