我收集几个,抛砖引玉,希望大伙补充,谢谢!

2．求第n个子集的所有元素
一个好汉三个帮，三个好汉九个帮，九个好汉二十七个帮，...停，今天不是让你算n个好汉几个帮（有兴趣的网友可以自己算），我们来看这个集合{ 1, 3, 9, 27, 81, ... }
这个集合是一个递增的无限集，每个元素都是3的幂。
我们把这个集合的所有子集按照元素和从小到大的顺序排好： {}(空集), { 1 }, { 3 }, { 1, 3 }, { 9 }, { 1, 9 }, { 3, 9 }, { 1, 3, 9 }, ...
现在给定一个正整数n，求第n个子集的所有元素，并按从大到小的顺序排列好
例：
n的值    结果
1        { }
4        { 3, 1 }
6        { 9, 1 }
500      { 6561, 2187, 729, 243, 81, 3, 1 }    

细节要求：
1. n的范围： n >= 1 ，unsigned int
2. 接口：    void HeroNeedThree(INT64* subset, unsigned int n);
   其中INT64是指64位整数，可以用 typedef long long INT64; 也可以自定义
   subset就是存放结果的数组，其中subset[0]存放结果子集的元素个数，
   然后子集元素从大到小存入subset[1],subset[2],......

算法分析：除去空集，观察前n个子集
{1}，----------------------------------------2^0 个子集
{3}，{1，3}，--------------------------------2^1 个子集
{9}，{1，9}，{3，9}，{1，3，9} --------------2^2 个子集
{27}，{1，27}，{3，27}，{1，3，27}，{9，27}，{1，9，27}，{3，9，27}，{1，3，9，27}----------------------------------------2^3 个子集
从上表可以看出对于有k个元素的集合，对应的有2^k（k<=32）个子集，而且每一行子集序列的第一个子集元素的大小恰好是3^0，3^1，3^2，3^3，…3^（k-1）。
我们把n转换成二进制数，当n=5时，它的二进制数为0000…0101（共32位），即2^0+2^2，对应的子集为{3^0，3^2}，即{1，9}；
当n=13时，它的二进制数为0000…1101（共32位），即2^0+2^2+2^3，对应的子集为{3^0，3^2，3^3}，即{1，9，27}；
由此可得，要求第n个子集（注意还要加上空集，实际上是第n+1个），则只需将其转换成32位的二进制，则它就是所求的子集的二进制序列。把二进制中值为1的位对应的元素作为3的指数，求出3的幂就是对应的元素。
根据此算法我们很容易的编出程序：
主函数：
#include <stdio.h>
#include <time.h>
#include <stdlib.h>

#define MAX_SIZE     ( 50 )

typedef long long INT64;

void HeroNeedThree(INT64* subset, unsigned int n);

int main(int argc, char *argv[])
{
        INT64 subset[MAX_SIZE] = {0};
        int i;
        
        for (int k=1; k<500; k++)
        {
        HeroNeedThree(subset, k);

        printf("%d: { ", k);
        for (i = 0; subset[i] > 0; ++i)
        {
                printf("%I64d, ", subset[i]);
        }
        printf("}\n");
        for (int i=0; i<MAX_SIZE; i++)
            subset[i] = 0;
       }

        system("pause");
        return 0;
}
功能函数：
INT64 Power(unsigned int x, unsigned int n)//求x的n次幂
{
    if (n == 0)
        return 1;
    INT64 s = Power(x, n/2);
    s *= s;
    if (n % 2 == 0)
        return s;
    else
        return s * x;
}

void HeroNeedThree(INT64* subset, unsigned int n)
{
    int t = 0;
    unsigned int m, s;
    
    n--;
    while (n > 0) //求n的二进制数的每一位
    {
        for (s=n,m=0; s>1; s>>=1)            
m++;
        subset[++t] = Power(3, m);
        n -= 1 << m;
    }
    subset[0] = t;
}

在上面的程序中，我们每次都要去求3的m次幂，虽然我们采用分治法求幂，速度较快，但是当n值教大时，还是需要很多时间的，因为long long类型是32位的，我们可以预先把3的0-31次幂全部求出来，存放在数组中，这样就不用每次都进行求幂运算了，可以节省不少时间。同样的，我们也可以把2的0-31次幂全部求出来，存放在数组中，这样就不必每次都去判断二进制数中各个1所在的位置，而直接用下标表示了。
改进后的代码如下：
void HeroNeedThree(INT64* subset, unsigned int n)
{
    // base3[k] = 3^k
    static INT64 base3[32] =
    {
0x1LL,0x3LL,0x9LL,0x1bLL,0x51LL,0xf3LL,0x2d9LL,0x88bLL,0x19a1LL,0x4ce3LL,0xe6a9LL,0x2b3fbLL,0x81bf1LL,0x1853d3LL,0x48fb79LL,0xdaf26bLL,0x290d741LL,0x7b285c3LL,0x17179149LL,0x4546b3dbLL,0xcfd41b91LL,0x26f7c52b3LL,0x74e74f819LL,0x15eb5ee84bLL,0x41c21cb8e1LL,0xc546562aa3LL,0x24fd3027fe9LL,0x6ef79077fbbLL,0x14ce6b167f31LL,0x3e6b41437d93LL,0xbb41c3ca78b9LL,0x231c54b5f6a2bLL
    };
    // base2[k] = 2^k
static unsigned int base2[32] =
{
0x1LL,0x2LL,0x4LL,0x8LL,0x10LL,0x20LL,0x40LL,0x80LL,0x100LL,0x200LL,0x400LL,0x800LL,0x1000LL,0x2000LL,0x4000LL,0x8000LL,0x10000LL,0x20000LL,0x40000LL,0x80000LL,0x100000LL,0x200000LL,0x400000LL,0x800000LL,0x1000000LL,0x2000000LL,0x4000000LL,0x8000000LL,0x10000000LL,0x20000000LL,0x40000000LL,0x80000000LL
    };
    INT64 num = 0;
    n--;
    for (int i=31; i>=0; --i)
    {
        if (n & base2[i]) // 计算n的第i位上是否是1
        {
            subset[++num] = base3[i];
        }
    }
    subset[0] = num;
}

3．丑陋数
    题目来自http://acm.pku.edu.cn/JudgeOnline/problem?id=1338，我做了一点小改动。
丑陋数是指质因数只包含2，3，5的自然数，例如前十个丑陋数依次为：1, 2, 3, 4, 5, 6, 8, 9, 10, 12。
给定一个自然数n (n <= 1500)，请你求出对应的第n个丑陋数。
函数接口：unsigned long UglyNumber(int n);
输入输出示例：
n = 2， 返回 2； n = 5， 返回 5；n = 7， 返回 8； n = 11， 返回 15；
解决此问题的一种思路就是先建立一个丑陋数表，把前1500个丑陋数全部求出来存储到数组lib[]中，这样只要返回lib[n-1]就好了。
本文分析一些建立丑陋数表的方法。
方法一：很容易想到判断一个数是否为丑陋数的方法，那就是判断它的因子是否只包含2，3，5。最简单的方法就是依次判断各个自然数，直到找齐1500个丑陋数为止。
代码如下：
#define MAX 500
unsigned long UglyNumber(int n)
{
    unsigned long lib[MAX] = {1,};//用来存储丑陋数表 
    unsigned long i, num;
    int k = 1;
    
    for (i=2; k<MAX; n++)
    {
        num = i;
        while (num % 2 == 0)
            num /= 2;
        while (num % 3 == 0)
            num /= 3;
        while (num % 5 == 0)
            num /= 5;
        
        if (num == 1)    //i是丑陋数 
            lib[k++] = i;    
    }

       return lib[n-1];
}   
程序很简洁的，也能得到正确的结果。但是当MAX大于1000的时候，程序就会超时。
原因是要逐个检查i，还要进行多次的求余运算，时间复杂度O（nlogn），当i很大时，耗时多。

方法二：利用任何一个丑陋数都是由比它小的丑陋数乘以2或3或5得到，可以利用已经求得的丑陋数表来判断一个数是否为丑陋数。
代码如下：
#define MAX 500

inline bool Find(const unsigned long lib[], int len, unsigned long data);

unsigned long UglyNumber(int n)
{
    unsigned long lib[MAX] = {1,2,3,4,5,};
    int k = 5;
    unsigned long i;
    
    for (i=6; k<MAX; i++)
    {
        if (i % 2 == 0 && Find(lib, k, i/2))//i能被2整除，且i/2是丑陋数 
            lib[k++] = i;
        else if (i % 3 == 0 && Find(lib, k, i/3))//i能被3整除，且i/3是丑陋数
            lib[k++] = i;
        else if (i % 5 == 0 && Find(lib, k, i/5))//i能被5整除，且i/5是丑陋数
            lib[k++] = i;    
    }
    
    return lib[n-1];
}   

inline bool Find(const unsigned long lib[], int len, unsigned long data)//判断data是否为lib[]的元素 
{
    int i;
    for (i=0; i<len && data>=lib[i]; i++)
    {
        if (data == lib[i])
            return true;        
    }
    return false;
} 

此方法看似比方法一要快，实际上因为每次都要遍历数组lib[]，所花时间比求余运算还多。时间复杂度为O（i*k），比方法一还要高。
看来，计算的瓶颈在于需要逐个判断自然数，当i的值很大时，耗时太多。能否不用排除法，而直接求出丑陋数表呢？我陷入了沉思。

方法三：为了便于分析，我把前50个丑陋数列出来。很快，我发现了规律：
观察数列：1
2 3 5
4 6 9 10 15 25
8 12 18 27 20 30 45 50 75 125
16 24 36 54 81 40 60 90 135 100 150 225 250 375 625
32 48 72 108 162 243 80 120 180。。。 
可以看出每行依次递增3，4， 5，6。。。个元素。以第2行为例，递增的元素分别是
4 = 2 * 2， 6 = 3 * 2， 9 = 3 * 3，后面三个元素10，15，25分别由2，3，5各乘以5得到；    
以第3行为例，递增的元素分别是
8 = 4 * 2， 12 = 6 * 2， 18 = 9 * 2，27 = 9 * 3；
后面六个元素20 30 45 50 75 125分别由4 6 9 10 15 25各乘以5得到；
由此可以得出规律：
设k表示栈顶，由于数组栈已经存储了4个元素{1,2,3,5,}，则k初始值为4。
设第n(n>1)行最左边元素的下标为left，最右边元素的下标为right-1，sum表示第n行的元素个数，其中n初始值为2，sum初始值为1。则对于第n行(n>1)来说，
 sum += n; left = k - sum; right = k;
 根据第n行的元素值，求出第n+1行的各个元素。
 其中前n-1个元素为  for (i=left; i<left+n; i++)
                 lib[k++] = lib[i] * 2;
 第n个元素为 lib[k++] = lib[left+n-1] * 3;
 后面的sum个元素为 for (; left<right; left++)    
            lib[k++] = lib[left] * 5;
依此类推，直到存储了足够的元素。
注意：此处不能以k==MAX为结束标志，因为数组的元素不是递增排列的，有可能遗漏前面较小的元素。
解决方案是宁多勿缺，增大k的取值，经测试当MAX=1500时，取MAX*9较好，注意同时设置lib[MAX*10]；
为防止溢出，把溢出的数值设置为0，注意即便数值很大，发生溢出，也不能跳出循环，因为k值必须递增，以满足前面总结出来的规律。
最后对得到的数组按递增排序，消去前面为0的元素。 
这样得到的丑陋数虽然远大于1500个，但因为时间复杂度不高，反而非常快，是典型的用空间换时间方法。
代码如下：
#define MAX 1500

int Move(unsigned long lib[], int len);
static int Compare(const void *p1, const void *p2); 

unsigned long UglyNumber(int n)
{
    unsigned long lib[MAX*10] = {1,2,3,5,};
    int left, right;
    int k = 4;
    int n = 2;
    int sum = 1;
    
    unsigned long max = MAX*9;        
    while (k < max)
    {
        sum += n;
        left = k - sum;
        right = k;
        
        int i;
        for (i=left; i<left+n; i++)
        {
            if (lib[i] * 2 < LONG_MAX)    //若数值太大（溢出），则取0 
                lib[k++] = lib[i] * 2;
            else
                lib[k++] = 0;
        }
        if (lib[left+n-1] * 3 < LONG_MAX)    //若数值太大（溢出），则取0 
            lib[k++] = lib[left+n-1] * 3;
        else
            lib[k++] = 0;
            
        for (; left<right; left++)    //若数值太大（溢出），则取0 
        {
            if (lib[left] * 5 < LONG_MAX)    
                lib[k++] = lib[left] * 5;
            else
                lib[k++] = 0;
        }                 
        n++;
    }

    qsort(lib, k, sizeof(unsigned long), Compare);//递增排列
    k = Move(lib, k); //去掉数值为0的元素 

    return lib[n-1];
}   

static int Compare(const void *p1, const void *p2)
{
    return (*(unsigned long *)p1) - (*(unsigned long *)p2);
}

int Move(unsigned long lib[], int len)
{
    int i = 0;
    while (lib[i] == 0)
        i++;
    
    int j = 0;
    while (i < len)
        lib[j++] = lib[i++];
        
    return j;
}

4．满足条件的m的个数
给出一个数字n和k，请找出有多少个不同的整数m满足： 
1） m<2^n 
2） m>=0 
3） |f(m,n)|<=k 
其中f(x,n)的定义如下： 
f(0,n)=n; 
f(x,n)=f([x/2],n),x为偶数 
f(x,n)=f([x/2],n)-2,x为奇数 

Input 
每组一行，分别给定n,k(1<=n<=62,2<=k<=5)

Output 
每组一行，给出满足条件的m的个数

Sample Input 
1 2
4 3

Sample Output 
2
14

主函数： 
#include <iostream>
#include <time.h>

using namespace std;

int Fun(int n, int k);

int main()
{
    time_t startTime;
    time_t endTime;
    time(&startTime);

    for (int i=1; i<=20; i++)
        for (int j=2; j<=5; j++)
            cout << i << "," << j << ": " << Fun(i, j) << "\t";
    cout << endl;
      
    time(&endTime);
    cout << difftime(endTime, startTime) << endl;

    getchar();
    return 0;
}

方法一：最直接的算法，根据题意递归求解。
int f(int x, int n)
{
    if (x == 0)
        return n;
    if ((x&1) == 0)            //x为偶数
        return f(x/2, n);
    else                    //x为奇数    
        return f(x/2, n) - 2;
}

int Fun(int n, int k)
{
    long long max = 1<<n;
    long long s = 0;
    
    for (int m=0; m<max; m++)
    {
        if (abs(f(m, n)) <= k)
            ++s;
    }
    return s;
}

方法二：以空间换时间，把所有的f(m, n)值存储到一个数组中,然后查表；由于max的值太大了，不可能建立这么大的数组，
但是可以建立一个较小的数组（长度为400000）， 存储对应的f(m, n)值，当m较小时，可以直接查表；
当m >= M时，递归减小m的值，直到m < M ，然后查表。
 void Table(int a[], int max, int n)//建立一个表，把所有的f(x, n)值存储到一个数组中
{
    a[0] = n;
    a[1] = n - 2;
    for (int i=2; i<max; i++)
    {
        if ((i&1) == 0)
            a[i] = a[i/2];
        else
            a[i] = a[i/2] - 2;
    }
}

long long Fun(int n, int k)
{
    const int M = 400000;
    int a[M];
    Table(a, M, n);//建表 
    
    long long max = 1<<n; //2^n
    long long s = 0;
    
    if (max < M)//当m较小时，可以直接查表
    {
        for (int m=0; m<max; m++)
        {
            if (abs(a[m]) <= k)
                ++s;
        }
    }
    else//当m >= M时，递归减小m的值，直到m < M ，然后查表
    {
        for (int m=0; m<M; m++)//先计算前面小于M的部分 
        {
            if (abs(a[m]) <= k)
                ++s;
        }
        long long t;
        int f;
        for (long long m=M; m<max; m++)//计算大于M的部分 
        {
            f = 0;
            t = m;
            while (t >= M)//递归减小m的值，累积奇数的个数，如果是奇数要减去2 
            {
                if ((t&1) == 1)
                    ++f;
                t >>= 1;
            }
            f = a[t] - f * 2;//查表
            if (abs(f) <= k)
                ++s;
        }
    }
    
    return s;
}

补充一个算法： 这是http://www.programfan.com/club/的sarrow得到的算法。 
由           | n;                 x == 0
f(x, n) = | f([x / 2], n);     x even number
          | f([x / 2], n) - 2; x odd number
观察x的二进制数，用ones_in_x表示x的二进制数中'1'的个数，zero_in_x表示x的二进制数中'0'的个数，
可以得到
f(x, n) = n - 2 * ones_in_x
        = n - 2 * (n - zero_in_x)
        = 2 * zero_in_x - n
所以|f(m,n)|<=k 就是 | 2 * zero_in_m - n | <= k
即     -k <= 2 * zero_in_m - n <= k
也即 (n - k) / 2 <= zero_in_m <= (n + k) / 2
又  0 <= m < 2^n
即满足条件的m，其二进制数中'0'的个数应该大于等于i，小于等于j，其中
      i = max{(n - k) / 2, 0};对(n - k) / 2应该四舍五入 
      j = max{(n + k) / 2, n};
所以求满足条件的m的个数，相当于解一个排列组合题目：分别求从n个'0'取出k个'0'的取法，
其中（i<=k<<j），再求所有取法之和， 
即  set_of_m = c(i, n) + ... + c(j, n);

int Gcd(int m, int n)//求最大公约数 
{
    int temp;
    
    while (n > 0)
    {
        temp = m % n;
        m = n;
        n = temp;
    }
    return m;
}

long long Combination(int m, int n)//求组合C(m, n)，注意不能直接按定义求，否则会溢出，先约分再除 
{    
    int *pm = new int[m];
    int *pn = new int[m];
    
    for (int i=0; i<m; ++i)
        pm[i] = i + 1;
    for (int i=0; i<m; ++i)
        pn[i] = n - i;
    
    int g;
    for (int i=0; i<m; ++i)
        for (int j=0; j<m; ++j)
        {
            g = Gcd(pm[i], pn[j]);//求最大公约数 
            pm[i] /= g;
            pn[j] /= g;
        }
        
    long long numerator = 1;
    long long denominator = 1;
    
    for (int i=0; i<m; ++i)
        numerator *= pn[i];
    for (int i=0; i<m; ++i)
        denominator *= pm[i];
        
    return numerator / denominator;
}

long long Fun(int n, int k)
{    
    int low  = (n < k) ? 0 : ((((n-k)&1) == 0) ? (n-k)/2 : (n-k)/2 + 1);
    int high = (n < k) ? n : (n+k)/2;
    long long s = 0;
    
    for (int i=low; i<=high; ++i)
        s += Combination(i, n);

    return s;
}

5．士兵站队
题目：训练场上n(1≤n≤50000)个高矮都不相同的士兵从左到右排成一行，依次编号为1，2，…，n。
第i个士兵的身高H(i)，由于采用特殊单位，H(i)满足1≤H(i)≤2000000000。
设第i个士兵右侧最近的比他个高的士兵编号为j，则第i个士兵可看到在他的右侧比他矮的士兵的个数S(i)=j-i-1。（不考虑客观因素，比如视力范围等-,-）
求S(1)+S(2)+…+S(n)。

输入：
标准输入。
第一行为整数n，表示士兵的个数。
第二行n个整数，用一个空格隔开。分别表示编号为1,2。。。n的士兵的身高

输出：
S(1)+S(2)+…+S(n)的结果

例：
输入
6
10 3 7 4 12 2
输出
5


主函数：
#include <iostream>
#include <time.h>

using namespace std;

int Sum(int h[], int n);

int main(void)
{
    time_t startTime;
    time_t endTime;
    const int n = 50000;
    int h[n] = {0};
    int temp, p;
    //获取互不相同的一组数列 
    for (int i=0; i<n; i++)
        h[i] = i + 1;
    for (int i=n-1; i>0; i--)//洗牌，使得数的大小随机排列 
    {
        p = rand()%i;
        temp = h[i];
        h[i] = h[p];
        h[p] = temp; 
    }
    //计时 
    time(&startTime);
    int s;
    for (int i=1; i<10000; i++)
        s = Sum(h, i);
    time(&endTime);

    cout << "sum = " << s << endl;
    cout << "time = " << difftime(endTime, startTime) << endl;
    
    system("pause");
       return 0;
}
方法一：根据题意可以得到一个很简单的算法，那就是遍历数组，依次累计每个元素右边比它小的元素，直到遇到比它大的元素为止。算法是时间复杂度为O（n^2）。
int Sum(int h[], int n)
{
    int sum = 0;
    for (int i=0; i<n; i++)
    {
        for (int j=i+1; h[j]<h[i] && j<n; j++)
            sum++;
    }
    return sum;
}
或者
int Sum(int h[], int n)
{
    int i, j;
    int sum = 0;
    for (i=0; i<n; i++)//从左到右遍历每一个士兵 
    {
        for (j=i+1; h[j]<h[i] && j<n; j++)//累计士兵右边比他矮的人数 
            ;
        sum += j - i - 1;//累积总人数 
    }
    return sum;
}

方法二：一个分治算法，思路和方法一一样，都是遍历数组，求出每一个S(i)，然后相加，区别在于不是从左到右依次计算，而是以当前的最高人为中心，分别计算其左右两边的人。算法是时间复杂度为O（n^2）。
int F(int h[], int low, int high)
{
    int i;
    for (i=low+1; h[i]<h[low] && i<high; i++)//累计士兵右边比他矮的人数 
        ;
    int sum = i - low - 1;
    if (i > low + 1)
        sum += F(h, low+1, i);
    if (i < high-1)
        sum += F(h, i, high);
    
    return sum;
}

int Sum(int h[], int n)
{
    F(h, 0, n);
}

方法三：以空间换时间，设置一个临时数组来存储原数组中的递减序列，依次将原数组中的元素与序列中元素比较，看是否可以将其插入到序列中。插入的法则为：若h[i] > temp[0]，即下一个士兵高度大于序列中任一高度，则用h[i]覆盖原序列中的所有元素，即top = 0;若h[i] < temp[top]，即下一个士兵高度小于序列中任一高度，这样只要将h[i]插入到序列的尾部，即++top;若不是上述两种情况，即h[i]只比序列中的一部分元素大，这样只要用h[i]覆盖原序列中的比它小的元素，我们在序列中找到h[i]的插入位置就可以了。最后更新序列的元素，并累积序列的长度。这样时间复杂度可以降低到O（n）。
这里借鉴了http://www.programfan.com/club/的yxs0001的代码，表示感谢！
int Insert(int h[], int n, int x)//二分法求插入的位置 
{
    int low = 0, high = n;
    int m;
    
    while (low <= high)//确保插入的位置是在low处，循环体最终总是执行low = m + 1; 
    {
        m = (low + high) / 2;
        if (h[m] > x)
            low = m + 1;
        else
            high = m - 1;
    }
    return low;
}

int Sum(int h[], int n)
{
    int *temp = new int[n];//设置一个临时数组来存储原数组中的递减序列 
    int top = 0;//临时数组栈顶
    int sum = 0; 
    int i; 
    
    temp[top] = h[0];
    for (i=1; i<n; i++)
    {
        if (h[i] > temp[0])//下一个士兵高度大于序列中任一高度
            top = 0;
        else if (h[i] < temp[top])//下一个士兵高度小于序列中任一高度 
            ++top;
        else                     //下一个士兵高度在序列中将其插入序列 
            top = Insert(temp, top, h[i]);
        
        temp[top] = h[i];
        sum += top;
    }
    
    delete []temp;
    
    return sum;
}

另外，http://www.programfan.com/club/的Kummerwu也写了一个很有趣的代码，他设置了一个结构，需要更多的空间，但是代码也更好理解，更高效。而且Kummerwu是一个很幽默的人，他幽默的注释，给程序带来了不少生趣。
typedef struct taller
{
    int h;      /* 第一个比自己高的士兵的身高 */
    int pos;    /* 该士兵的位置 */
}TALLER;

//说白了，就是一个出栈，入栈的过程，每个元素入栈一次，在入栈的过程中，
//可以将比自己小的元素踢出栈，所以最坏情况下，所有元素入栈，出栈各操作一次
//故复杂度为O(n)
int Sum(int h[], int n)
{
    const int MAX_SOLDIER_CNT = 50000;
    const int MAX_SOLDIER_H = 2000000000;
    static TALLER talls[MAX_SOLDIER_CNT + 2]; //高个子俱乐部
    TALLER * cur_tall = talls;
    int count = 0;

    cur_tall->h = MAX_SOLDIER_H + 1; //标兵(靠，这家伙还真高呀)
    cur_tall->pos = n;
    
    for (n-=2; n>=0; n--)
    {
        //如果我比右侧的那个家伙高(俺也算个高个子了)
        if (h[n] > h[n+1]) 
        {
            //把比自己矮的士兵踢出栈,(呵呵，爽! )
            while (cur_tall->h < h[n]) 
            {
                cur_tall--; //这里可能有优化的空间??可以用二分法插入 
            }

            //算算中间有几个矮冬瓜(现在cur_tall是第一个比我高的家伙)
            count += cur_tall->pos - n - 1;

            //呵呵，俺光荣的加入高个子俱乐部了 :).
            cur_tall++;   
            cur_tall->h = h[n];
            cur_tall->pos = n; 
        }
        //靠，右侧那家伙比我高
        //(算了，让他进入高个子堆吧,反正也没啥油水可以捞)
        else 
        {
            cur_tall++;
            cur_tall->h = h[n+1];
            cur_tall->pos = n+1;
        }
    }
    
    return count;
}

好东西 支持一下

支持下~[em4][em16]

发现有我的程序哦~

从长远来看空间换时间是明智的选择，只有在一些空间不富裕的时候稍候收敛下就行了