只有76分啦，求解解决思路

只有76分啦，求解
给一个正整数数列，每个数都在100万内，最多100万个数，有一个动作叫“插入”，就是把某个数从原来位置拿出来，插到某个新的位置，就像整理扑克牌那样，问给你的这个数列要多少次插入才能非递减地排列好。就输出这个次数。比如5 1 2 3 4，就插入一次即可

[解决办法]
相当于求最长递增子序列，复杂度为O(nlogn)。
[解决办法]
http://blog.csdn.net/bobcowwocb/archive/2009/09/09/4536092.aspx

水平有限，看不懂，悲剧了。
[解决办法]

C/C++ code

  
 #include <stdio.h> 
 #include <string.h> 
 #include <stdlib.h> 
 int f[100001],a[100001],c[100001]; 
 int n,size; 
 int bsearch(int ai) 
 { 
 int l=1,r=size,mid; 
  while (l <=r) 
  {//二分查找 
    mid=(l+r)>>1; 
    if (ai <c[mid-1] && ai>=c[mid]) return mid; 
    else if (ai <c[mid]) l=mid+1; 
    else r=mid-1; 
  } 
 } 
 int main() 
 { 
  scanf("%d",&n); 
  if (!n) 
  { 
    printf("0\n"); 
    exit(0); 
  } 
  for (int i=1;i <=n;i++) scanf("%d",&a[i]); 
  f[1]=1;c[1]=a[1];size=1; 
  for (int i=2;i <=n;i++) 
  { 
    if (a[i]==0) continue; 
    int j; 
    if (a[i]>=c[1]) j=1; 
    else if (a[i] <c[size]) j=++size; 
    else j=bsearch(a[i]); 
    f[i]=j;c[j]=a[i]; 
  } 
  printf("%d\n",size); 
  system("pause"); 
  return 0; 
 }             
  
 本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/bobcowwocb/archive/2009/09/09/4536092.aspx 
  
 

//上边for循环里部分和下边的推理貌似不太一样，很郁闷，大家看看for循环里边是不是写错了。
***********************************************************************************
注意到D[]的两个特点：

(1) D[k]的值是在整个计算过程中是单调不上升的。
(2) D[]的值是有序的，即D[1] < D[2] < D[3] < ... < D[n]。

利用D[]，我们可以得到另外一种计算最长上升子序列长度的方法。设当前已经求出的最长上升子序列长度为len。先判断A[i]与D[len]。若A[i] > D[len]，则将A[i]接在D[len]后将得到一个更长的上升子序列，len = len + 1， D[len] = A[i]；否则，在D[1]..D[len]中，找到最大的j，满足D[j] < A[i]。令k = j + 1，则有D[j] < A[i] <= D[k]，将A[i]接在D[j]后将得到一个更长的上升子序列，同时更新D[k] = A[i]。最后，len即为所要求的最长上升子序列的长度。


本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/bobcowwocb/archive/2009/09/09/4536092.aspx
[解决办法]
这个 得学习以下
[解决办法]

探讨

这个次数就等于最长不降子序列的长度？

查看更多 下一篇