JDOJ 2157 Increasing

洛谷 P3902 递增

洛谷传送门

JDOJ 2157: Increasing

JDOJ传送门

Description

数列A1，A2，……，AN，修改最少的数字，使得数列严格单调递增。

Input

第1 行，1 个整数N
第2 行，N 个整数A1，A2，……，AN

Output

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

Sample Input

3 1 3 2

Sample Output

1

HINT

• 对于50% 的数据，N <= 103
• 对于100% 的数据，1 <= N <= 105， 1 <= Ai <= 109

最优解声明

8ms卡的我好苦

题解：

这是一道单调队列的题。

首先我们想到这样的一个定理：

我们先维护一个单调队列，这个队列的元素是严格单调递增的，那么，现在我们要增加一个元素的时候，先与队尾元素比较，如果比队尾元素大，OK，入队。否则的话，就把这个元素插入到它应该到的位置，使这个东西还是一个单调队列。这时就进行了修改操作，我们就需要把答案++。

于是我们敏锐的察觉到，把这个元素插入到它应该到的地方是这道题的难点。

然后我们又敏锐地察觉到，可以用二分解决。

于是有了代码1：

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

但是这个方法很麻烦。麻烦就在于必须全部读入之后再处理，需要跑两边循环，无数遍二分。所以我们想到了在讲二分地时候学习的lower_bound和upper_bound函数，它们是我们实现二分的有利帮手。

代码2：

#include<cstdio>
#include<algorithm>
using namespace std;
int n,q[100001],now,ans;
int main()
{
    scanf("%d",&n);

    for(int i=1;i<=n;i++)
    {
        int num;
        scanf("%d",&num);
        if(num>q[now])
            q[++now]=num;
        else
        {
            *lower_bound(q+1,q+now+1,num)=num;
            ans++;
        }
    }
    printf("%d",ans);
    return 0;
}