3627 - 倒置表
时间限制 : 1 秒
内存限制 : 128 MB
{ A1,A2,……}是一个排列的集合{ 1,2,…n }。给定序列A：a1,a2,a3....，an，如果i<j且ai>aj则(ai,aj)称为序列A的
一个倒置。
之后引出了序列的倒置表
例如：给出序列A： 5,9,1,8,2,6,4,7,3
则其倒置表为：2 3 6 4 0 2 2 1 0；
这里倒置表的第一个数据是2，则表示在序列A中与1形成倒置的有两个即：(5,1) (9,1)，以此类推。。
也所以你的任务是将其倒置表的排列,或反之亦然,从一个反演表转换到相应的置换。
题目输入
输入包含多个测试用例。每个测试用例包含两行。
第一行包含一个整数(1 < = N < = 9)这表明置换/颠倒的元素数量表。
第二行始于足下特征“P”,这意味着接下来的N个整数形式排列,或“I”,也就是说,接下来的N个整数形式一个倒置表。
以下是N个整数,用空格分开。输入终止行包含N = 0。
题目输出
对于每个输入输出一行隔一个空格.如果输入是一个排列,输出将相应的反演表;如果输入是一个反演表,你的输出将
会相应的置换。
输入/输出样例
输入格式
9 P 5 9 1 8 2 6 4 7 3 9 I 2 3 6 4 0 2 2 1 0 0
输出格式
2 3 6 4 0 2 2 1 0 5 9 1 8 2 6 4 7 3
C++解答
#include <stdio.h> int main() { //freopen("test.in.txt","r",stdin); //freopen("test.out","w",stdout); int n,i,j,k,m,y; while(scanf("%d",&n)!=EOF&&n!=0) { int a[n]; int b[n]; char c; for(i=0;i<n;i++) b[i]=0; scanf("%c",&c); for(i=0;i<n;i++) scanf("%d",&a[i]); if(c=='P') { for(i=0;i<n;i++) { k=i+1; y=0; while(k--) { if(a[i]<a[k]) y++; } b[a[i]-1]=y; } for(i=0;i<=n-1;i++) { if(i==0) printf("%d",b[i]); else printf(" %d",b[i]); } printf("\n"); } else if(c=='I') { for(i=0;i<n;i++) { j=0; k=i+1; m=a[i]; while(m+1) { if(b[j]==0) m--; j++; } b[j-1]=k; } for(i=0;i<n;i++) { if(i==0) printf("%d",b[i]); else printf(" %d",b[i]); } printf("\n"); } } return 0; }