??????????

#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<30000; i++)
        s = Sum(h, i);
    time(&endTime);

    cout << "sum = " << s << endl;
    cout << "time = " << difftime(endTime, startTime) << endl;
    
    system("pause");
       return 0;
}

int Sum(int h[], int n)
{
    int sum = 0;
    int i, t;//i作为原数组元素的下标，用来遍历原数组；t表示临时数组的长度-1 
    int *a = new int[n];//设置一个临时数组来存储原数组中的递减序列 
    
    a[0] = h[0];
    for (t=0,i=1; i<n; i++)
    {
        if (h[i] < h[i-1])//如果是递减序列，复制到临时数组，并累积S(i)之和 
        {
            a[++t] = h[i];
            sum += t;
        }
        else//如果出现一个比其左边的人高的士兵 
        {
            while (t > 0 && a[t-1] < h[i])//该士兵左移，直到队伍最左或者遇到比他高的人 
                t--;
            a[t] = h[i];
            sum += t;//累积S(i)之和 
        }
    }
    
    delete []a;
    
    return sum;
}

试试看呵呵
/****************************************************************** 
** 文件名: Programfan.cpp
** 创建人: tiantangniao223
** 日 期:  2007 03 23
** 修改人: 
** 日 期: 
** 描 述: 程序的输入采用标准输入，如果输入的士兵的身高个数超出士兵的人数
**        程序将忽略超出的数据处理
** 版 本: 1.1
**----------------------------------------------------------------------------- 
******************************************************************/ 

#include<iostream> 
using namespace std;

int main()
{
    int  n=0;//士兵的人数
    int  i=0,j=0;//循环变量
    int  count=0;//用于记录比当前士兵矮的士兵人数
    int sum=0;//符合条件的士兵总数 
    cout<<"请输入士兵人数n(1<=n<=50000):"<<endl;
    cin>>n;
    while(n<1||n>50000)//检查士兵人数 n 是否合法
    {
        cout<<"输入n不符合要求!!!!!"<<endl;
        cout<<"请重新输入士兵个数:(1<=n<=50000)"<<endl;
        cin>>n;
    }
    long *H=new long[n+1];
    for(i=0;i<=n;i++)//初始化分配的数组
        H[i]=0;
    cout<<"请输入的士兵身高H(1<=H<=2000000000):"<<endl;
    for(i=1;i<=n;i++)
        cin>>H[i];
    for(i=1;i<=n;i++)//检查士兵的身高是否有小于1或是大于2000000000的数据
    {
        while(H[i]<1||H[i]>2000000000)
        {
            cout<<"输入的士兵身高不符合要求!!!"<<endl;
            cout<<"输入的士兵身高中有小于1或是大于2000000000的数据!"<<endl;
            cout<<"请重新输入 "<<n<<" 个士兵的身高:(1<=H<=2000000000)"<<endl;
            for(j=1;j<=n;j++)
                cin>>H[j];
        } 
    }
    for(i=1;i<=n;i++)//检查士兵的身高中是否有相等的数据
    {
        for(j=i+1;j<=n;j++)
        {
            if(H[i]==H[j])
            {
                cout<<"输入的士兵身高不符合要求!"<<endl;
                cout<<"输入的士兵身高中有相等的数据!!!"<<endl;
                cout<<"请重新输入 "<<n<<" 个士兵的身高:(1<=H<<2000000000)"<<endl;
                for(j=1;j<=n;j++)
                     cin>>H[j];
                break;
            }
        }
    }
    for(i=1;i<=n;i++)//进行比较
    {
        for(j=i+1;j<=n;j++)
        {
            if(H[i]<H[j])//如果右侧有比他高的，则结束本次比较
                break;
            count++;
        }
        sum+=count;
        count=0;
    }
    cout<<sum<<endl;
    delete[] H;
    return 0;
}

试试看呵呵
/****************************************************************** 
** 文件名: Programfan.cpp
** 创建人: tiantangniao223
** 日 期:  2007 03 23
** 修改人: 
** 日 期: 
** 描 述: 程序的输入采用标准输入，如果输入的士兵的身高个数超出士兵的人数
**        程序将忽略超出的数据处理
** 版 本: 1.1
**----------------------------------------------------------------------------- 
******************************************************************/ 

#include<iostream> 
using namespace std;

int main()
{
    int  n=0;//士兵的人数
    int  i=0,j=0;//循环变量
    int  count=0;//用于记录比当前士兵矮的士兵人数
    int sum=0;//符合条件的士兵总数 
    cout<<"请输入士兵人数n(1<=n<=50000):"<<endl;
    cin>>n;
    while(n<1||n>50000)//检查士兵人数 n 是否合法
    {
        cout<<"输入n不符合要求!!!!!"<<endl;
        cout<<"请重新输入士兵个数:(1<=n<=50000)"<<endl;
        cin>>n;
    }
    long *H=new long[n+1];
    for(i=0;i<=n;i++)//初始化分配的数组
        H[i]=0;
    cout<<"请输入的士兵身高H(1<=H<=2000000000):"<<endl;
    for(i=1;i<=n;i++)
        cin>>H[i];
    for(i=1;i<=n;i++)//检查士兵的身高是否有
    {                //小于1或是大于2000000000的数据
        while(H[i]<1||H[i]>2000000000)
        {
            cout<<"输入的士兵身高不符合要求!!!"<<endl;
            cout<<"输入的士兵身高中有小于1或是大于2000000000的数据!"<<endl;
            cout<<"请重新输入 "<<n<<" 个士兵的身高:(1<=H<=2000000000)"<<endl;
            for(j=1;j<=n;j++)
                cin>>H[j];
        } 
    }
    for(i=1;i<=n;i++)//检查士兵的身高中是否有相等的数据
    {
        for(j=i+1;j<=n;j++)
        {
            if(H[i]==H[j])
            {
                cout<<"输入的士兵身高不符合要求!"<<endl;
                cout<<"输入的士兵身高中有相等的数据!!!"<<endl;
                cout<<"请重新输入 "<<n<<" 个士兵的身高:(1<=H<<2000000000)"<<endl;
                for(j=1;j<=n;j++)
                     cin>>H[j];
                break;
            }
        }
    }
    for(i=1;i<=n;i++)//进行比较
    {
        for(j=i+1;j<=n;j++)
        {
            if(H[i]<H[j])//如果右侧有比他高的，则结束本次比较
                break;
            count++;
        }
        sum+=count;
        count=0;
    }
    cout<<sum<<endl;
    delete[] H;
    return 0;
}

这次代码经过精心提炼，绝对是最优化的。。。

#include <stdio.h>

int Height[50000];

int main()
{
    int offset,sum,i;

    scanf("%d",Height);
    getchar();
    for(i=1;i<=Height[0];i++)
        scanf("%d",Height+i);

    Height[i]=2000000001;

    sum=0;
    for(i=1;i<=Height[0];i++)
    {
        offset=1;
        while(Height[i]>Height[i+offset++]);
        offset-=2;
        sum+=offset;

    }
    printf("%d",sum);
    return 0;
}

//O(n) 的算法
// while循环实际执行的次数最多为n, 有兴趣的同学自己分析一下

#include <stdio.h>
#include <memory.h>

#define MAX    50004

static int h[MAX];
static int prev[MAX];
static int S[MAX];

int main()
{
    memset(prev, 0, sizeof(prev));
    memset(S, 0, sizeof(S));

    int i,j;
    int n;
    int count = 0;

    scanf("%d", &n);
    h[0] = 2000000001;
    for (i=1; i<=n; i++)
    {
        scanf("%d", &(h[i]));
        j = i-1;
        while (h[i] > h[j])
            j = prev[j];
        prev[i] = j;
    }

    for (i=n; i>0; i--)
    {
        count += S[i];
        j = prev[i];
        S[j] = S[j] + S[i] + 1;
    }

    printf("%d", count);
    return 0;
}

看看答案

#define MAX_SOLDIER_CNT 50000
#define MAX_SOLDIER_H   2000000000

typedef struct taller
{
    int h;      /* 第一个比自己高的士兵的身高 */
    int pos;    /* 该士兵的位置 */
}TALLER;


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

    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;

}

#include<iostream>
#include<stdlib.h>
using namespace std;
unsigned int CountHeight(int n,unsigned long *H)  //函数的具体实现
{//1
    unsigned int max[100]={0},next=0,count=0,i,j=0;
    int m,sta;//重复次数
    long temp;
    for(i=1;i<n;i=max[j]+1)
     {//2
  loop:temp=H[max[j]]-H[i];
       next=i+1;
    // cout<<"##"<<endl;                    //*****************
       if(temp<0)                            //交换接力棒
           max[j]=i;
           
       else if(temp>0)                      //传递比较大小
         {//3
           {
            count++;
       //   cout<<count<<endl;               //********************
           }
           m=1;
           while(next<=n)                   //传递大小具体实现
             { //4
                temp=H[i]-H[next];
      //       cout<<"**"<<endl;          //***********************
                if(temp<0)
                  {//5
       // ***************************************

                   for(sta=j;sta>=0;sta--)
       //****************************************
                      {
                      temp=H[max[sta]]-H[next];
                      m--;                      //取消累加
                      if(temp<0)
                         {max[sta]=next;m--;i++;goto loop;}    //交换接力棒,退出循环
                      else if(temp>0)
                         {
                          i++;next++;j++;           //后移比较
                          m++;                     //恢复原始
                          count+=m;
          //              cout<<count<<endl;       //********************8
                          break;
                         } //
                      }
                  }//5
                else if(temp>0)
                   {
                   i++;next++;               //后移比较
                   m++;                      //进行累加
                   count+=m;
         //        cout<<count<<endl;         //**********************
                   continue;
                   }
             }//4
         } //3
     }//2
     return count;
}

int main(void)
{
    cout<<"请输入人数:";                  //确定人数
    int Num=0;
    cin>>Num;
    cout<<"请输入每位的身高:"<<endl;      //输入身高
    
    
    unsigned long Height[Num];
    for(int i=0;i<Num;i++)
       cin>>Height[i];
    unsigned int count=0;
    
    
    count=CountHeight(Num,Height);      //函数接口统计数目
    cout<<count<<endl;
    
    
    system("pause");
    return 0;
}
/******************************************************
我的算法就是让前一个数a[i]去减后面的一个数a[i+1],如果前面的比后面的大,就
让a[i+1]与a[i+2]比较,如果还是前面的大,就记录值+2,否则就记录+1,利用他们的
传递性,如果前一个总比后一个大,那么只需要扫描一遍,因为他的次数可以1+2+……+n
来计算。相反，如果在传递过程中发现后一个比前一个大，那么只需要和前面区间
的最大数比较就可以了，相应的记录值-1就可以了。
例如：
10 5 7 4 12 2
先定义最大为10，10-5  ——记录+1
然后 5-7<0  —— 10-7 ——记录+1
然后 7-4>0  ---- 记录+2
然后 4-12<0 ---- 7-12<0 ---10-12<0 ----记录+0  大于0跳出,小于0记录--
然后 12-2>0 ---- 记录+1  */

#include<iostream>
using namespace std;
const int MaxCount = 50000;        // 存放士兵身高数组的最大值
void main()
{
    long SoldierHeight[MaxCount];  // 存放士兵身高的数组(2^31-1)
    int  SoldierCount;             // 实际士兵个数
    long i,j;                      // 循环变量    
    int  Sum = 0;                  // 输出结果(计数器)        

    // 获得用户输入的值
    cin >> SoldierCount;
    for(i=0;i!=SoldierCount;++i)
    {
        cin >> SoldierHeight[i]; 
    }

    // 计算结果
    for(i=0;i!=SoldierCount-1;++i)
    {
        long MaxHeight;
        int  nCount = 0;               // 第i个士兵可看到右侧比他矮的士兵个数
        for(j=i+1;j!=SoldierCount;++j)
        {
            MaxHeight = SoldierHeight[j];            
            if(MaxHeight > SoldierHeight[i])
            {
                break;
            }
            else
            {
                nCount++;
            }
        }
        Sum = Sum + nCount;
    }
    cout << Sum << endl; 
}