主题：第51次编程比赛
renew [专家分：200] 发布于 2007-03-22 18:02:00
题目：训练场上n(1≤n≤50000)个[b][color=FF0000]高矮都不相同[/color][/b]的士兵[b]从左到右[/b]排成一行，依次编号为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
例子说明：
S(1) = 3
S(2) = 0
S(3) = 1
S(4) = 0
S(5) = 1
S(6) = 0
S(1)+S(2)+S(3)+S(4)+S(5)+S(6) = 3+0+1+0+1+0 = 5
最后更新于：2007-03-26 00:19:00
回复列表 （共65个回复）
61 楼
neverPE [专家分：1620] 发布于 2007-03-25 19:55:00
--------------------------------------------------------------------------------
内容隐藏，本帖结帖后才能浏览。
--------------------------------------------------------------------------------
62 楼
forjane [专家分：5670] 发布于 2007-03-25 20:29:00
常规算法啦,时间复杂度0(n),最少比较n-1次,最差比较2n-3次
#include <stdio.h>
long CountShort(long n, long *height)
{
long *cnt, i, j, tmp;
long sum = 0;
cnt = (long *)malloc(sizeof(long)*n);
memset(cnt, 0, sizeof(long)*n);
for(i = n-2; i >= 0; i--)
{
for(j = i+1; j < n && height[i] > height[j]; j += tmp)
{
tmp = cnt[j]+1;
cnt[i] += tmp;
}
sum += cnt[i];
}
free(cnt);
return sum;
}
int main()
{
long a[9]={19,2,60,30,50,55,40,33,52};
printf("%d\n",CountShort(9,a));
getch();
return 0;
}
63 楼
leander [专家分：0] 发布于 2007-03-25 21:10:00
#include<iostream>
using namespace std;
int findError(int n ,int* arr){//to find error in member[i]
for(int i=0;i<n;i++){
if (arr[i]<=0)
return 1;
}
return 0;
}
int main(){
int n;
while(1){
cout<<"Pls enter a positive number --->";
cin>>n;
if(n<=0){
cout<<"Error!!!"<<endl;
continue;
}else break;
}
int member[n];
cout<<"Pls enter ["<<n<<"] members next line:"<<endl;
while(1){
for(int k=0;k<n;k++){
cin>>member[k];
}
int pd=findError(n,member);
if(pd==1){
cout<<"You get an error!!!"<<endl;
cout<<"Pls enter ["<<n<<"] members with all positive numbers! Try again:"<<endl;
continue;
}else
break;
}
int temp=0;
int s;
for(int i=0;i<n-1;i++){
for(int j=i+1;j<n;j++){
if(member[i]<member[j]){
s=j-i-1;
cout<<"######s = "<<s<<endl;//display the s
temp+=s;//add s
break;
}else{
if(j==n-1){
s=j-i;
cout<<"******s = "<<s<<endl;//display the s
temp+=s;//add s
break;
}else{
continue;
}
/*
if member[i]>=member[j],continue to find the number which is bigger then member[i],end if none of all number is bigger then member[i],then add all numbers after member[i].
*/
}
}
}
cout<<"The total S(i) is--->"<<temp<<endl;
return 0;
}
64 楼
w01fdawn [专家分：30] 发布于 2007-03-25 23:20:00
#include <iostream>
using namespace std;
int main()
{
int num;
int numH;
int i=0;
int sum=0;
double h[50000];
cin>>num;
numH = num;
if ( numH<1 )
exit(1);
while (numH != 0)
{
cin>>h[i];
if(h[i]<1)
exit(1);
i++;
numH--;
}
for(int j=0; j<num; j++)
{
for(int k=j+1; k<num; k++)
{
if(h[j]>h[k])
{
sum++;
}else{break;}
}
}
cout<<sum;
return 1;
}
65 楼
雨中飞燕 [专家分：18980] 发布于 2007-03-26 00:18:00
到这里应该是结束了吧。。。后面的帖子已经是不能再提交答案了吧。。。。
我来回复
您所在位置：