当年toj存在的时候，我也做过这题，4年前吧

推箱子那个就不管它了，但导弹这个有更快的方法我感兴趣，我有想过，但没想也更快的方法，能说下更快方法的思路吗？麻烦你了，谢谢！

http://hi.baidu.com/starwing/blog/item/6418423464910049251f14ce.html

打个广告

进了ls的大人的广告里一看封面才意识到，原来您是想把UserYuH姐姐调教成女仆啊



（学习了膜拜）

看了你给的解说，头都蒙了，还是看你之前给的代码好点。
我仔细琢磨，算法很精典，我之前的代码如对处理多的数据，速度上就慢了，算法也有问题，希望楼主没研究我的代码。StarWing83我把你放的代码注释了说明，看下我理解的对不对。
·
另外说下，楼上的，我是帅哥，不是姐姐。
·
·

#include <stdio.h>
#include <stdlib.h>

#define N 100
int n, a[N], bn, b[N], c[N], d[N];
/* 数组a：保存输入的数，所在导弹的高度
   数组b：保存最长降序数列，但不是最终结果。
   数组c：保存数组b降序数列在a中的下标。
   数组d：记下每段降序的连接下标，最主要就是这数组，只了解了这数组里的数据，了解程序是怎么把每一段数列对应的下标保存下来，这个算法就想通了。就这点难。
  变量bn：记下降序数列长度 */

int main(void)
{
    int i, cur;

    while (scanf("%d", &n) == 1) /* 先输入有几棵导弹n */
    {
        for (i = 0; i < n; ++i) /* 对n个导弹指定高度 */
            scanf("%d", &a[i]);
        for (i = 0, bn = -1; i < n; ++i)/* 降序数列长度初始值为：-1，循环n次 */
        {
            if (bn == -1 || a[i] <= b[bn])/* bn等于-1时，表示测到第一棵导弹，长度bn增1，保存高度到数组b。
                                         a[i]<=b[bn],指如测到当前导弹的高度比前一棵低，bn增1，保存这棵的高度到数组b */
                b[cur = ++bn] = a[i];
            else /* 否则测到的当前导弹高度大于前一棵，下面的算法是把这棵的高度插入有序的数组b里，准确的说是：找到插入点，复盖
掉这点。 */
            {
                int low = 0, high = bn, mid;
                while (mid = (low + high) >> 1, low + 1 < high)
                {
                    if (a[i] < b[mid])
                        low = mid;
                    else if (a[i] >= b[mid])
                        high = mid;
                }
                if (b[low] <= a[i])
                    b[cur = low] = a[i];
                else
                    b[cur = high] = a[i];
            }
            c[cur] = i;/* 保存刚入数组b的值在数组a的下标 */
            d[i] = cur ? c[cur - 1] : -1;/* 记下连接，这不好理解，如各位自己编写同样算法的程序就会知道难点在这 */
        }
        cur = c[bn];/* 到这是以找到最长的降序数列了，把这数列最后的一个数，也最小的数的下标赋给cur */
        for (i = bn; i >= 0; --i)/* 循环把最长的降序数列保存到数组b，了解数组d，这循环才好了解。 */
        {
            b[i] = a[cur];
            cur = d[cur];
        }
        for (i = 0; i <= bn; ++i)/* 输出可击落最多导弹的各个高度，也是就是最长数列 */
            printf("%d ", b[i]);
        putchar('\n');
    }
    return 0;
}

[ 本帖最后由 UserYuH 于 2009-10-7 00:12 编辑 ]

是个逆序的问题吧，
要使输出的高度，
逆序为0.
300 275 252 200 138

建义楼上的可以动手编个试试，这题并不那么容易。

基本是理解正确了。不过有些小细节需要特别注意。

首先，那个二分搜索是真正的难点，如果这个二分搜索写错了（哪怕差了一个位置），那也算是挂了。首先这个搜索是寻找[bo]恰好小于等于欲插入元素的左数第一个位置[/bo]。因此，我让其在欲插入元素小于中间元素的时候，向右搜索（注意是low = mid。而不是low = mid + 1，这一点很重要）,反之，向左搜索。这样，最后的结果，就是low和high在相邻的两个空间内，然后分别判断。这段代码没有考虑效率，但求无过，设计时需要特别留意。

其次，就是你说的d数组了。这个其实很好理解，只要你理解了整个算法。我们先看看，b数组是什么呢？其实，b数组是当前（在插入了当前元素a[i]以后）的“临时的”最长不上升序列。这个序列有个特点。假设有两个数字a[i]和a[j]，a[j]在a[i]后面，但是她们两个在b数组的“排位”相同（注意，这个的意思是，她们两个的“临时的”最长不上升序列的长度相同）。那么，在以后的判断中，我们选择a[i]继续下去好，还是选择a[j]继续下去好呢？显然选择她们之间比较大的好。为什么？假设a[i]是4，a[j]是5，而整个序列最小的元素是1，这样如果选择a[i]，则下一个元素有1,2,3,4四种选择，而如果选择了a[j]，则下一个元素有五种选择！选择得越多，这个序列就可以持续地越长，你可以想像是用一系列的杆子“撑起”一块布，显然杆子越高，撑起来的距离就越长，是不是？

理解了上面的关键的思想，就明白了其实d数组是用来记录第i个元素在其最长不上升序列中的前一个元素的位置的。这样就像糖葫芦一样，一个串一个，如同链表一样可以找到所有的值了（对于本题，其实可以省掉c和d数组，直接输出bn即可，因为题目只要求输出可拦截导弹的最大数目而已）。

给User一个小小的题目：你能不能重新设计那个二叉搜索，在保持正确性的同时，让其形式更加优雅？

我只觉得要了解d数组比了解二分搜索要难，刚又测试了下，程序还有点小问题。
如输入：300 200 180 160 180 180 160
则输出是：300 200 180 160 160
正确应该是：300 200 180 180 180 160
·
这应该就是你说的对二分法的应用要注意的问题
·
你要我重新设计二分法搜索，我想不出更优雅的，只改正了上面的错误。
·

·
·
while (low + 1 < high) 
    { 
      mid = (low + high) >> 1;/* 这个取中间值循环条件判断用不上，我把它移下来了。这样让人更好理解点 */  
      if (a[i] <= b[mid])   /* 加个等号 */
           low = mid; 
      else if (a[i] > b[mid]) /* 原先有一个等号，现在去掉了 */
           high = mid; 
     } 
    if (b[low] < a[i])   /* 原先这也有一个等号，现在去掉了，这样测试数据都正确了。  */
       b[cur = low] = a[i]; 
    else
       b[cur = high] = a[i];
      · 
      ·  

[ 本帖最后由 UserYuH 于 2009-10-7 16:35 编辑 ]

额，写的那么仔细，还是算漏了地方……哎~~~

恩，你改的两个地方都是对的。另外，可以去掉另一个if，单纯一个if已经可以判断了……

while (low + 1 < high)
    {
      mid = (low + high) >> 1;/* 这个取中间值循环条件判断用不上，我把它移下来了。这样让人更好理解点 */  
      if (a[i] <= b[mid])   /* 加个等号 */
           low = mid;
      else
           high = mid;
     }
    if (b[low] < a[i])   /* 原先这也有一个等号，现在去掉了，这样测试数据都正确了。  */
       b[cur = low] = a[i];
    else
       b[cur = high] = a[i];