1320 inversion.cpp

威士忌的HDU题解.大概有260多题的源码。对于学习非常有好处。

//求逆序数 ， 并按所得表倒推得出原表 
#include <cstdio>
using namespace std;
int pt[51],it[51];

int main()
{
	int i,j,k,n;
	char opnd;
	
	while( scanf("%d",&n)!=EOF && n)
	{
		scanf("%c",&opnd);
		scanf("%c",&opnd);
		if(opnd=='P')
		{
			for(i=1;i<=n;i++)
				scanf("%d",&pt[i]) , it[i]=0;
				
			for(i=2;i<=n;i++)
				for(j=i-1;j>=0;j--)
					if( pt[j] > pt[i] )
						it[ pt[i] ]++;
				
			for(i=1;i<=n;i++)
				if(i!=n)
					printf("%d ",it[i]);
				else
					printf("%d\n",it[n]);
		}
		else
		{
			for(i=1;i<=n;i++)
				scanf("%d",&it[i]) , pt[i]=0;
				
			for(i=1;i<=n;i++)
				for(j=1;j<=n;j++)
				{
					if(pt[j]==0)
						if(it[i]>0)
							it[i]--;
						else
						{
							pt[j]=i;
							break;
						}
				}
			
			for(i=1;i<=n;i++)
				if(i!=n)
					printf("%d ",pt[i]);
				else
					printf("%d\n",pt[n]);
		}
	}
	return 0;
}