题意：数列A1,A2,...,AN，修改最少的数字，使得数列严格单调递增。(1<=N<=10^5; 1<=Ai<=10^9 )
思路：首先要明白的一点是数列是严格单调递增，那么没有修改的最长上升子序列也是严格单调递增的，并且是满足要求的。
何为满足要求？ 假设A（a）---B（b）---C（c）……是一个符合要求的不修改序列，括号内为下标，那么有B-A>=b-a，这样才能满足夹在中间的数能够修改。
那么本题在nlogn求最长上升子序列的基础做一些处理即可。
处于满足的序列中必须有a[i]-lis[x]-1>=i-pos[x]-1，并且替换的时候不是原来的找到大于这个值的最小的，而是找满足前面这个式子已求序列中最大的。
比如序列：1 3 6 6 13 2 8 9 10，求最长上升子序列过程中当求得的序列为 1 3 6 13 时，当遇见8时，我们不是变为1 3 6 8，而是变成1 3 8， 因为只有这样才是满足条件的，当时它的最长序列top=4不会变化。
还要注意的一点是lis[0]初始化为-oo，因为a[i]可以修改为负数。
1 #include<cstdio> 2 #include<iostream> 3 using namespace std; 4 5 const int maxn=100005; 6 const int oo=0x3fffffff; 7 int a[maxn]; 8 int lis[maxn], pos[maxn]; 9 10 int main() 11 { 12 int n; 13 while(cin >> n) 14 { 15 for(int i=1; i<=n; i++) scanf("%d",a+i); 16 int top=0; 17 lis[0]=-oo; 18 for(int i=1; i<=n; i++) 19 { 20 if(a[i]>lis[top]&&a[i]-lis[top]-1>=i-pos[top]-1) 21 { 22 lis[++top]=a[i]; 23 pos[top]=i; 24 } 25 else 26 { 27 int l=0, r=top, tp=-1; 28 while(l<=r) 29 { 30 int mid=(l+r)>>1; 31 if(a[i]-lis[mid]-1>=i-pos[mid]-1) 32 { 33 tp=mid; 34 l=mid+1; 35 } 36 else r=mid-1; 37 } 38 if(tp!=-1) lis[tp+1]=a[i], pos[tp+1]=i; 39 } 40 } 41 cout << n-top <<endl; 42 } 43 return 0; 44 } 45 /* 46 5 47 1 6 6 7 8 48 7 49 1 2 2 2 2 2 7 50 9 51 1 3 6 6 13 2 8 9 10 52 13 53 1 2 2 3 10 6 6 6 6 6 7 8 9 54 11 55 1 2 3 4 10 10 7 8 9 10 10 56 */