ZOJ Problem Set

题目：这道题目的意思让人猛地一读有点反应不过来，简单解释下：

给定序列A：a1,a2,a3....，an，如果i<j且ai>aj则(ai,aj)称为序列A的一个倒置。

之后引出了序列的倒置表（主要这里有点不好理解），即由序列A可以得到序列B：b1,b2,b3...,bn，序列B满足在第J个上的数据bj表示所有在A序列中与j可以形成倒置的个数。

例如：题目给出的序列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.给定原有序列计算倒置表；

2.给定倒置表计算出原有序列。

思路：问题1较为简单，直接用一个O(n^2)的循环遍历统计下就行

问题2的话有点绕但是也不难，例如给定倒置表B：2 3 6 4 0 2 2 1 0，则顺序遍历该倒置表，当i为1时b[i]=2，则从第一个空位开始数起，数够2个，1的位置在原序列中应该是第三个，因为任何正整数都可以和1形成倒置，所以前面两个数字既可以和1形成两个倒置；i=2时b[i]=3，则从第一个空位开始数起，数够3个，隔开1，把2放在第5个位置上，以此类推。

解答：见代码

#include <stdio.h>

int main()
{
    int N,i,I[60],O[60];
    while(scanf("%d",&N)!=EOF&&N)
    {
        getchar();
        char flag;
        scanf("%c",&flag);
        
        for(i=1;i<=N;i++)
            scanf("%d",&I[i]);
        if(flag=='P')
        {
            for(i=1;i<=N;i++)
            {    
                int num=0;
                for(int j=1;j<=N;j++)
                {
                    if(I[j]==i)
                        break;
                    if(I[j]>i)
                        num++;
                }
                O[i]=num;
            }
        }
        else
        {
            for(i=1;i<=N;i++)
                O[i]=-1;
            for(i=1;i<=N;i++)
            {
                int num=0;
                for(int j=1;j<=N;j++)
                {
                    if(!I[i])
                    {
                        if(O[j]==-1)
                        {
                            O[j]=i;
                            break;
                        }
                        else
                            continue;
                    }
                    else
                    {
                        if(num==I[i])
                        {
                            if(O[j]==-1)
                            {
                                O[j]=i;
                                break;
                            }
                            else
                                continue;
                        }
                        if(O[j]==-1)
                        {
                            num++;
                        }
                    }
                }
            }
        }
        for(i=1;i<N;i++)
            printf("%d ",O[i]);
        printf("%d
",O[i]);
    }

    return 0;
}