[GRYZ2015]INCR

题目描述

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

输入格式

第 1 行，1 个整数 N

第 2 行，N 个整数 A1,A2,...,AN

输出格式

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

样例输入

3

1 3 2

样例输出

1

数据范围

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

对于 100% 的数据，1 ≤ N ≤ 10^5,1 ≤ Ai ≤ 10^9

思路

　　需要用O(NlogN)的最长上升子序列。需要改几个小地方。

　　有一个注意问题，就是改的数能不能是实数，我本来没有考虑这个情况，写了一个本来错误的程序，不过后来居然奇迹的卡过了所有点。(⊙o⊙)

　

机房断电了，代码没了，就这样吧。

STD:

#include<cstdio>
#include<iostream>
using namespace std;

const int maxn=100005;
const int oo=0x3fffffff;//极大值
int a[maxn];
int lis[maxn], pos[maxn];

int main()
{
    int n;
    while(cin >> n)
    {
        for(int i=1; i<=n; i++) scanf("%d",a+i);
        int top=0;
        lis[0]=-oo;
        for(int i=1; i<=n; i++)
        {
            if(a[i]>lis[top]&&a[i]-lis[top]-1>=i-pos[top]-1)
            {
                lis[++top]=a[i];
                pos[top]=i;
            }
            else
            {
                int l=0, r=top, tp=-1;
                while(l<=r)
                {
                    int mid=(l+r)>>1;
                    if(a[i]-lis[mid]-1>=i-pos[mid]-1)
                    {
                        tp=mid;
                        l=mid+1;
                    }
                    else r=mid-1;
                }
                if(tp!=-1) lis[tp+1]=a[i], pos[tp+1]=i;
            }
        }
        cout << n-top <<endl;
    }
    return 0;
}