51Nod 1294 修改数组 —— LIS

题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1294

1294 修改数组 

题目来源： HackerRank

基准时间限制：1 秒 空间限制：131072 KB 分值: 160 难度：6级算法题

 收藏

 关注

给出一个整数数组A，你可以将任何一个数修改为任意一个正整数，最终使得整个数组是严格递增的且均为正整数。问最少需要修改几个数？

Input

第1行：一个数N表示序列的长度(1 <= N <= 100000)。
第2 - N + 1行：每行1个数，对应数组元素。(0 <= A[i] <= 10^9)

Output

输出最少需要修改几个数使得整个数组是严格递增的。

Input示例

5
1
2
2
3
4

Output示例

3

题意：

给出一个数列，问至少修改多少个数，使得序列：全为正整数且严格单调递增。

题解：

1.首先，不需要修改的数构成了这个数列的“骨架”，这个“骨架”且满足：b[i].val-b[j].val>=b[i].index-b[j].index， i>j，这条不等式限制了在骨架点i和j之间，必须有足够范围的数。

2.可知第一个数最小为1，第二个数最小为2，……第i个数最小为i。

3.根据第2点，可以得出一个结论：当a[i]<i时，a[i]必须修改；当a[i]>=i时，a[i]可能不需要修改。

4.所以将可能不需要修改的数（包括数值和其所在的位置）提取出来，放到结构体数组b[]当中，然后求b[]数组的LIS（需满足：b[i].val-b[j].val>=b[i].index-b[j].index， i>j），即为整个序列的“骨架”，在“骨架上”的数都不需要修改，所以：ans = n - LIS_LEN 。

代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <set>
using namespace std;
typedef long long LL;
const int INF = 2e9;
const LL LNF = 9e18;
const int MOD = 1e9+7;
const int MAXN = 1e5+10;

struct node
{
    int val, pos;
};
node a[MAXN], dp[MAXN];

bool ok(node x, node y)
{
    return (x.val-y.val)>=(x.pos-y.pos);
}

int Search(node dp[], int n, node x)
{
    int l = 1, r = n;
    while(l<=r)
    {
        int mid = (l+r)>>1;
        if(ok(x,dp[mid]))
            l = mid + 1;
        else
            r = mid - 1;
    }
    return r;
}

int main()
{
    int n, m;
    while(scanf("%d", &n)!=EOF)
    {
        for(int i = 1; i<=n; i++)
            scanf("%d",&a[i].val);
        m = 0;
        for(int i = 1; i<=n; i++)
            if(a[i].val>=i)
                a[++m].val = a[i].val, a[m].pos = i;

        int len = 0;
        for(int i = 1; i<=m; i++)
        {
            if(i==1||ok(a[i],dp[len]))
                dp[++len] = a[i];
            else
            {
                int pos = Search(dp,len,a[i]);
                dp[pos+1] = a[i];
            }
        }
        printf("%d
", n-len);
    }
}