ZOJ-1201* 排列与逆序数相互转换

逆序数:在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。

如:
P 5 9 1 8 2 6 4 7 3
I 2 3 6 4 0 2 2 1 0

1前面比1大的有2个
2前面比2大的有3个
3前面比3大的有6个。。。。

1201：在permutation 和inversion之间转换。

思路:P-->I
双重循环,对每个数统计前面比它大的有几个

I-->P
双重循环。从最小的开始排起，每次从头扫描，给比它大的值留下空位。

#include<stdio.h>
#include<memory.h>
#include<iostream>
using namespace std;


int res[51];
int src[51];

void P2I(int n)
{
	int count=0;
	for(int i=1;i<=n;i++)
	{
		count=0;
		for(int j=1;j<=n;j++)
		{
			if(src[j]>i)
				count++;
			else if(src[j]==i)
				break;
		}
		res[i]=count;
	}
}

void I2P(int n)
{
	memset(res,0,sizeof(int)*51);
	int count=0;
	for(int i=1;i<=n;i++)
	{
		count=0;
		for(int j=1;j<=n;j++)
		{
			if(res[j]==0)
				count++;
			if(count>src[i])
			{
				res[j]=i;
				break;
			}
		}
	}
}

int main()
{
	int n;
	char type;
	while(1)
	{
		cin>>n;
		if(n!=0)
		{
			cin>>type;
			for(int i=1;i<=n;i++)
				cin>>src[i];

			if(type=='P')
				P2I(n);
			else if(type=='I')
				I2P(n);
		}
		else
			break;
		for(int i=1;i<n;i++)
			cout<<res[i]<<' ';
		cout<<res[n]<<endl;
	}
	
	
}