ZOJ 1201 Inversion

原题链接

题目大意：给一个数组{ A1,A2,…,An } ，要求生成另一个数组B1,B2,…,Bn，使得Bi表示的是在数组A中排在i前面大于i的数字的个数。题目的输入是数组A（字母P表示）或者数组B（字母I表示），要求输出对应的B或者A。

解法：先读取首字母，如果是P，则调用permutation（），反之调用inversion（）。permutation是按照正常方法寻找。inverse是先设置一个空的数组（相当于A数组），按照B数组的顺序一个个往‘A’中放。

参考代码：

#include<iostream>
using namespace std;void permutation();
void inversion();
int i,j,n,a[50],b[50];int main(){
char c;
while(cin>>n && n!=0){
cin>>c;
for(i=0;i<n;i++)
cin>>a[i];
if(c=='P')
permutation();
else if(c=='I')
inversion();
}return 0;
}void permutation(){
for(i=0;i<n;i++){
b[i]=0;
for(j=0;j<n;j++){
if(a[j]>i+1)
b[i]++;
if(a[j]==i+1)
break;
}
}
for(i=0;i<n-1;i++)
cout<<b[i]<<' ';
cout<<b[n-1]<<'\n';
}void inversion(){
int num,p;
for(i=0;i<n;i++)
b[i]=0;
for(i=0;i<n;i++){
num=a[i];
p=0;
while(num>=0){
if(b[p]==0)
num--;
p++;
}
b[--p]=i+1;
}
for(i=0;i<n-1;i++)
cout<<b[i]<<' ';
cout<<b[n-1]<<'\n';
}