这一题题目有些长,不过这不影响它是一道水题。
题意描述:
题中描述了两种情况,当输入数据以'P'开头时,表示输入的是1~N的一个排列,要求输出每个数前面比该数大的数字的个数,输出结果时顺序为数字1的在前,数字N的在最后。第二种情况正好相反,给出每个数字前面比该数大的数字的个数,要求输出原序列。
第一种情况好说,主要是第二种情况。情况二的解法是按从后往前顺序确定原序列,即先确定数字N的位置,再确定数字N-1的位置……直到所有数字位置确定。期间主要是元素的插入操作。
#include<stdio.h>
#include<stdlib.h>
#define LEN 60
int num[LEN]; //输入,
int rs[LEN];//所求结果,两种情况的结果都用rs[]记录。
int N;
void fP()
{
int i, j, k;
int ps;
for(i = 1; i <= N; i++)
{
ps = 0;
while(num[++ps] != i);
int count = 0;
for(k = 1; k < ps; k++)
if(num[k] > i)
count++;
rs[i] = count;
}
}
void Insert(int ps, int insertnum, int len)//插入函数
{
int i, j;
for(i = len; i >= ps; i--)
rs[i + 1] = rs[i];
rs[ps] = insertnum;
}
void fI()
{
int i, j;
int len;
rs[1] = N;
len = 1;
for(i = N - 1; i >= 1; i--)
{
int ps = num[i] + 1;
Insert(ps, i, len);
len++;
}
}
int main()
{
int i, j;
char c;
scanf("%d", &N);
while(N != 0)
{
getchar();
c = getchar();
for(i = 1; i <= N; i++)
scanf("%d", &num[i]);
if(c == 'P')
fP();
else
fI();
for(i = 1; i < N; i++)
printf("%d ", rs[i]);
printf("%d\n", rs[i]);
scanf("%d", &N);
}
//system("pause");
}
posted on 2012-08-02 16:19
小鼠标 阅读(220)
评论(0) 编辑 收藏 引用 所属分类:
水题