//Visual C++6.0 - Win32 console Application
#include <stdio.h> //输入输出库函数
#include <time.h>  //用于简单计时
#define MAX      50000         //士兵最大数目
#define UINT     unsigned long //无符号长整数
UINT nHei[MAX],nCt[MAX];

//函数接口 CountShort：*pHeight士兵高度数组 nCount士兵个数
UINT CountShort(UINT *pHeight,UINT nCount)
{
    UINT *p=pHeight+nCount-1,*pH=nHei+1,*pC=nCt;
    *nHei=0xFFFFFFF;*pH=*p--;*pC=0; //初始化
    for(nCount=0;p>=pHeight;p--) //开始统计
    {
        UINT c=0;
        while(*p>*pH)c+=*pC+1,pH--,pC--;
        *++pH=*p;nCount+=*++pC=c;
    }
    return nCount;
}
int main()
{
    UINT n1,nRT,n=6;            //n为士兵个数
    UINT h[MAX]={10,3,7,4,12,2};//h为士兵高度(定量测试)
    //scanf("%lu",&n);getchar();     //手动输入数据:士兵个数n
    //for(n1=0;n1<n;n1++)scanf("%lu",&h[n1]);//手动输入士兵高度
    //long t = clock();      //取当前时间（单位ms）
    //for(n1=0;n1<10000000;n1++)          //重复执行测试
        nRT=CountShort(h,n);              //接口调用
    //printf("Time:%ld\n",clock()-t);     //输出运行时间差
    printf("%lu\n",nRT);                  //输出结果
    return 0;
}

附加说明：//注释掉的代码可按需去掉注释符来测试
另附自动检bug数据生成代码(加在士兵高度对数组h初始化的地方)：
    for(UINT z1=0,z2;z1<n;z1++)//n是士兵个数
    {
        z2=1000000*(3-z1%3)+MAX;//3可改为更大，一般足够了
        h[z1]=z2 - z1;//加或减看算法写
        //从左到右的算法用减号，反之用加号
    }

[code]
#include <iostream>
#include <stack>
using namespace std;

struct Sod{
    long long height;
    int can_see;
    Sod();
};
Sod::Sod():height(0),can_see(0){}

bool operator>(const Sod& lhs, const Sod& rhs) {
    return lhs.height > rhs.height;
}
stack<Sod> sod_queue;
//__int64 height_list[50010];
long long height_list[50010];

int main()
{

    long long sum = 0;
    int n;
    cin >> n;
    int i;
    for (i = 0; i < n; ++i) {
        cin >> height_list[i];
    //    scanf("%I64d", &height_list[i]);
    }
    Sod dummy;
    for (i = n - 1; i >= 0; --i) {
        int tmp = 0;
        dummy.height = height_list[i];
        while(!sod_queue.empty() && !(sod_queue.top() > dummy)) {
            tmp += sod_queue.top().can_see + 1;
            sod_queue.pop();
        }
        dummy.can_see = tmp;
        sum += tmp;
        sod_queue.push(dummy);
    }
    cout << sum << endl;
//    printf("%I64d\n", sum);
    return 0;
}

[/code]

__int64 i,sun=0,j;
for(i=0;i<n;i++)
 {
   for(j=i+1;j<n;j++)
       if(a[i]<a[j])
        {sun+=j-i-1;break;}
 }

#include <iostream>
using namespace std;

/**
 * 算法说明:为了求解s(i),首先将士兵i与士兵i+1的高度进行比较,如果
 * 士兵比士兵i+1要矮,即H(i)<H(i+1),则s(i)=0;如果H(i)>H(i+1),若
 * s(i+1)!=0,说明从H(i+2)至H)(i+s(i+1))都小于H(i+1),也就必然小于
 * H(i),s(i)加上s(i+1)后,继续和H(i+s(i+1)+1)做进一步的比较;若
 * s(i+1)等于0,则s(i)加1后,继续与s(i+2)进行比较,依次类推.
**/
int main(int argc, char* argv[])
{
    int nSoldiers; // 士兵人数
    int *arrayHeight = NULL; // 士兵高度数组
    int *arrayResult = NULL; // 保存s(i)结果数组
    int nCount = 0; // 最后结果

    cout << "输入" << endl;
    cin >> nSoldiers;

    arrayHeight = new int[nSoldiers];
    for( int i = 0;  i < nSoldiers; i++)
        cin >> arrayHeight[i];

    arrayResult = new int[nSoldiers];
    memset(arrayResult, 0, nSoldiers * sizeof(int)); // 将值初始化为0

    // 从倒数第二个士兵开始计算s(i)
    for( int nCur = nSoldiers - 1; nCur > 0; nCur-- )
    {
        int nFlag = nCur + 1; // 下一个要比较的士兵位置
        while( nFlag <= nSoldiers && arrayHeight[nCur -1] > arrayHeight[nFlag - 1] )
        {
            if(arrayResult[nFlag -1] != 0)
            {
                arrayResult[nCur] += arrayResult[nFlag -1];
                nFlag += arrayResult[nFlag -1];
            }
            else
            {
                arrayResult[nCur]++;
                nFlag++;
            }
        }
    }
    for( i = 0; i < nSoldiers; i++ )
    {
        nCount += arrayResult[i];
    }

    cout << "输出" << endl << nCount <<endl;

    return 0;
}

偶解决不了2000000000000那么多,还是写了int之内的参与一下,不要笑话哦[em8]


#include <cstdlib>
#include <iostream>

using namespace std;
int NUMBERS;
int S;
int Si;

int main(int argc, char *argv[])
{
    cout<<"请输入士兵的个数："<<endl;
    cin>>NUMBERS;

    int array[NUMBERS];
   for(int i=0;i<NUMBERS;i++)
   {
           cin>>array[i];
   }
   
   int temp;

   for(int i=0;i<NUMBERS;i++)
   {
        temp=array[i];
         
        for(int j=i+1;j<NUMBERS;j++)
        {       
                //cout<<"以第"<<i<<"为基准，用第"<<j<<"来比较"<<endl;
                //cout<<"基准"<<temp<<endl;
                if(array[j]<=temp)
                {
                     //cout<<"here"<<endl;
                     if(j==NUMBERS-1)
                     {
                         //cout<<"here"<<endl;
                         Si=j-i;                    
                         S+=Si;
                         //cout<<i<<" "<<j<<" "<<Si<<" "<<S<<endl;
                        break;             
                     }
                     continue;                  
                }
                else
                     {
                        Si=j-i-1;                    
                        S+=Si;
                        temp=array[i+1];
                         //cout<<i<<" "<<j<<" "<<Si<<" "<<S<<endl;
                        break;
                     }
                     
               
        }              
       // cout<<"基准变成:"<<temp<<endl;
   }
    cout<<S<<endl;
    system("PAUSE");
    return 0;
}




//偶第一次参加比赛,不当之处前辈们指正哈;

挺有意思的，学习一下

#include<iostream>
using namespace std;

void compare(int height[], int record[], int i, int j)  {
    if (height[i]>height[j]) {
        record[i]=record[i]+record[j]+1;  //记录i点能看几个
        compare(height,record,i,j-record[j]-1); //跳去j点看不到的点继续比较
      }
}

int main()  {
    int n;
    cin>>n;
    int* height=new int[n+1];
    int* record=new int[n+1];
    for(int i=0;i<n+1;i++) record[i]=0;
    for(int i=n;i>0;i--) cin>>height[i];   //翻转的话等于向左看
    height[0]=2000000001;        //设置停止比较点
    for(int i=1;i<=n;i++)
        compare(height,record,i,i-1);
    for(int i=1;i<=n;i++)
        record[0]=record[0]+record[i];
    cout<<record[0]<<endl;
    delete []height;
    delete []record;
   } //没有验证输入数据的合法性 呵呵~

昨天在火车站等车坐了两个钟头　无聊了想想　终于有点改进
虽然貌似有铅套循环　不过想想应该比0（n^2）要快吧　直接写了个main:
#include <iostream>
using namespace std;
main()
{
    int n;
    int i;
    int S(0);
    int sum(0);
    int zhan[1000];
    int data[50000];
    cin>>n;
    for(i=0;i<n;i++)
        cin>>data[i];
    for(i=0;i<n;i++)
    {
        while(S>0&&data[i]>zhan[S-1])
        {
            sum=sum+S-1;
            S--;
        }
        zhan[S++] = data[i];
    }
    S--;
    for(;S>0;S--)
    {
        sum+=S;
    }
    cout<<sum<<endl;
}

#include<stdio.h>

#define MAX 50000

int main()
{
    int n,m,i,H[MAX],r[MAX],sum=0;          
    scanf("%d",&n);
    printf("输入:\n%d\n",n);

    for(i=0;(scanf("%d",&m))&&(m>1)&&(m<2000000000);++i){
        H[i]=m;
        printf("%d  ",H[i]);
        if(i==(n-1))
            break;
    }

    for(i=0;i<n;++i)
        for(int j=i+1;j<n;++j){
            r[i]=0;
            if(H[i]>H[j])
            r[i]++;
            else if((H[i]<H[j])||(H[i]==H[j]))
                break;
            sum+=r[i];
        }
    printf("\n输出:\n%d",sum);
    return 0;
}

#include"stdio.h"
#define num1 50000
#define num2 2000000000
main()
{
  int N,result=0;
  int i,j,k;
  long h[num1],s[num1];
  
  while(1){
     printf("Enter a number for n (n>=1 && n<=%d): ",num1);
     scanf("%d",&N);
     if(N>=1&&N<=num1) break;
     printf("Error - the n you entered is not valid.\n");
  }

  while(1){
     printf("\nEnter a group of number for soldier's height (height>=1 && height<=%d):\n",num2);
     for(i=0;i<N;i++){
    scanf("%d",&h[i]);
    if(h[i]>=1&&h[i]<=num2){  k=1;continue;}
    printf("Error - the group the you entered is not valid.\n");
    break;
     }
     if(k==1) break;
  }

  for(i=0;i<N;i++){
    for(j=i+1;j<N+1;j++){
        if(h[i]>h[j]) continue;
        s[i]=(j-i-1);
        result+=s[i];
        break;
    }
  }
  printf("the result is:%d\n",result);
  return 0;
}