主题：第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个回复）
31 楼
zljc [专家分：0] 发布于 2007-03-23 16:59:00
#include <iostream.h>
#include <stdlib.h>
struct list
{
int num;
struct list *next;
};
typedef struct list type;
typedef type *link;
void main()
{
int i,n;
link head;
link pre1;
head=(link)malloc(sizeof(type));
head->next=NULL;
pre1=head;
cout<<"输入士兵个数:";
cin>>n;
for(i=0;i<n;i++)
{ cin>>pre1->num; //输入士兵身高
pre1->next=(link)malloc(sizeof(type));
pre1->next->next=NULL;
pre1=pre1->next;
}
int temp1,temp2;
int sum=0,count=0;
link pre2;
link jtemp;
pre1=head;
pre2=head;
pre2=pre2->next;
while(pre1->next!=NULL)
{
temp1=pre1->num;
temp2=pre2->num;
jtemp=pre2; //保存指向
while(temp1>temp2)
{
if(pre2->next!=NULL)
{
pre2=pre2->next;
temp2=pre2->num;
count++;}
else
break;
}
pre2=jtemp; //恢复原指向
sum=sum+count;
count=0;
pre1=pre1->next;
pre2=pre2->next;
}
cout<<sum<<'\n';
}
32 楼
medie2005 [专家分：30] 发布于 2007-03-23 17:33:00
#include <iostream>
using namespace std;
int sum=0;
int *list;
void fun(int f,int e)
{
if( f==e )
return ;
int i, Max=list[ f ], Maxpos=f;
for( i=f; i<=e; ++i )
{
if( list[ i ]>Max )
{
Max=list[ i ];
Maxpos=i;
}
}
sum=sum+e-Maxpos;
if( Maxpos>f )
fun(f,Maxpos-1);
if( Maxpos<e )
fun(Maxpos+1,e);
return ;
}
int main()
{
int len;
cin>>len;
list=new int[ len ];
int i;
for( i=0; i<len; ++i )
cin>>list[ i ];
fun( 0, len-1 );
cout<<sum<<endl;
system("PAUSE");
delete [ ]list;
return 1;
}
33 楼
flyee [专家分：340] 发布于 2007-03-23 19:18:00
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
int main()
{
vector<double> height;
stack<int> index;
int n,res;
double ftemp;
while(cin>>n&&n){
res=0;height.clear();while(!index.empty()){index.pop();}
for(int i=0;i<n;i++){
cin>>ftemp;
height.push_back(ftemp);
for(;!index.empty()&&(ftemp>height[index.top()]);index.pop()){
res+=(i-index.top()-1);
}
index.push(i);
}
for(;!index.empty();index.pop()){
res+=(n-index.top()-1);
}
cout<<res<<endl;
}
return 0;
}
34 楼
lewsn2008 [专家分：1010] 发布于 2007-03-23 19:33:00
#include <stdio.h>
#define N 5000
long n;
long a[N];
long count(int s)
{
int i, p, sum;
p = a[s];
sum = 0;
for(i=s+1; i<n; i++)
{
if(a[i] < p) ++sum;
else break;
}
return sum;
}
void main()
{
int i, sum = 0;
printf("\nPlease Input n(1~50000): ");
scanf("%d", &n);
while(!(1<n && n<50000)) scanf("%d", &n);
printf("Please Input %d numbers(long):", n);
for(i=0; i<n; i++)
{
scanf("%d", &a[i]);
}
for(i=0; i<n; i++)
sum += count(i);
printf("The result is: %d\n", sum);
}
35 楼
wuzsh [专家分：180] 发布于 2007-03-23 20:48:00
#include<iostream>
using namespace std;
int main()
{
long n;
cin >> n;
long *Height=new long[n];
if(Height==NULL)
{
cout << "Out of space" << endl;
exit(0);
}
for(long i=0; i<n; i++)
{
cin >> Height[i];
}
long Sum=0;
for(long i=0; i<n; i++)
{
for(long k=i+1; Height[k]<Height[i] && k<n; k++)
{
Sum++;
}
}
cout << Sum << endl;
delete []Height;
}
36 楼
sunseed [专家分：20] 发布于 2007-03-23 21:18:00
#include <iostream>
using namespace std;
__int64 f(int n,int *height){
int * stack = new int [n];
int top,index;
__int64 count = 0;
top = 0;
index = 0;
*(stack + top) = index;
top++;
index++;
while(index < n){
if(* (height + *(stack + top -1)) > *(height + index)){
*(stack + top) = index;
top++;
index++;
}
else{
while(top > 0 && *(height + *(stack + top -1)) < *(height + index)){
count += (__int64)(index - *(stack + top -1) - 1);
top--;
}
*(stack + top ) = index;
top++;
index++;
}
}
if(top <= 1){
delete []stack;
return count;
}
for(int i = top - 1;i >= 1;i--)
count += (__int64)( *(stack + top -1) - *(stack + i -1) );
delete []stack;
return count;
}
int main(int argc, char* argv[])
{
int n;
cin>>n;
while(n){
int * height = new int [n];
for(int i = 0;i < n;i++)
cin>>*(height + i);
printf("%I64d\n",f(n,height));
delete []height;
cin>>n;
}
return 0;
}
37 楼
xchbcahz [专家分：50] 发布于 2007-03-23 21:48:00
//using VC++6.0
#include "stdafx.h"
#include <iostream>
#define MAX 50000
using namespace std;
unsigned int S(unsigned int n,unsigned long h[])
{
unsigned int i,j;
unsigned int result=0;
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
if(h[i]<=h[j])
break;
else
result++;
return result;
}
int main(int argc, char* argv[])
{
cout<<"请输入整数的个数n:";
unsigned int n;
unsigned long h[MAX];
cin>>n;
cout<<"请输入"<<n<<"个整数:";
for(int i=0;i<n;i++)
cin>>h[i];
cout<<"结果为:"<<S(n,h)<<endl;
return 0;
}
38 楼
绿吗甲都不能用 [专家分：0] 发布于 2007-03-23 21:49:00
#include "stdio.h"
main()
{
int j,i,sum=0,n,k=1;
long int h[50],d,max=0;
printf("please input the number of the Soldier(n<=5000):");
scanf("%d",&n);
for( i=1; i<=n; i++ )
{
scanf("%ld",&d);
h[i]=d;
if (d>max) {max=d;k=i;}
for(j=k ; j<i; j++ )
{ if(h[j]!=0&&h[j]>h[i])
sum++;
if(h[j]<h[i]) h[j]=0; }
}
printf("%d",sum);
}
39 楼
kirby2004 [专家分：0] 发布于 2007-03-23 22:54:00
#include<stdio.h>
int counter(int n,int a[])
{
int i,j,sum=0;
for(i=0;i<=n-1;i++)
{for(j=i+1;j<=n-1;j++)
{if(a[i]>a[j])
sum++;
else
break;
}
}
return sum;
}
main()
{ int a[50]={0};
int i,num,n,*p;
p=&a[0];
printf("input n:");
scanf("%d",&n);
for(i=0;i<=n-1;i++)
{printf("please input the height of the soldier:");
scanf("%d",&a[i]);
}
num=counter(n,p);
printf("%d",num);
return 0;
}
40 楼
oaiei [专家分：1490] 发布于 2007-03-23 23:04:00
#include <stdio.h>
const int N = 50001;
struct INFO{
int i, h;
}s[N];
int main()
{
int i, top, sum, tmp, n;
while(scanf("%d", &n) != EOF){
for(i = sum = 0, top = -1; i < n; i++){
scanf("%d", &tmp);
while(top >= 0 && tmp > s[top].h)
sum += (i - s[top--].i - 1);
s[++top].i = i;
s[top].h = tmp;
}
while(top >= 0)
sum += (n - s[top--].i - 1);
printf("%d\n", sum);
}
return 0;
}
输入输出用freopen就好了。。
我来回复
您所在位置：