南郵-1214-並べ替えの辞書順の問題

1343 ワード

並べ替えられた辞書順の問題
時間制限(通常/Java):1000 MS/3000 MS         実行メモリ制限:65536 KByte
コミット合計:84           テスト合格:21
説明
n個の要素{1,2,...,n}はn!個の異なる配列.これをn!個の配列を辞書順に並べ、0,1,...,n!-1.各配列の番号は、辞書の順序値です.例えば、n=3の場合、6つの異なる配列の辞書シーケンス値は以下のようになる.
ディクショナリ順序値  0      1      2      3       4      5
整列       123    132   213  231  312   321
nおよびn個の要素{1,2,...,n}の配列を与え,この配列の辞書順値と辞書順に配列された次の配列を計算した.
入力
入力データの1行目は要素個数nである.次の1行はn個の要素{1,2,...,n}の配列である.
しゅつりょく
算出された配列の辞書順値と辞書順の次の列、1行目が辞書順値、2行目が辞書順の次の列を出力します. 
サンプル入力
8 2 6 4 5 8 1 7 3
サンプル出力
8227 2 6 4 5 8 3 1 7
テーマソース
アルゴリズム設計と実験問題解
コード:
#include <iostream>
#include <algorithm>
using namespace std;
__int64 Factorial(int n)
{
    __int64 Ans=1;
    int i;
    for (i=2; i<=n; i++) Ans=Ans*i;
    return Ans;
}
int main()
{
    __int64 Ans=0;
    int i,n, Seq[15];

    cin>>n;
    for ( i=0; i<n; i++)
        cin>>Seq[i];
    for ( i=0; i<n; i++)
    {
       int Count=0;
       for (int j=i+1; j<n; j++)
           if (Seq[j]<Seq[i]) Count++;
       Ans=Ans+Factorial(n-i-1)*Count;
    }
    cout<<Ans<<endl;
    next_permutation(Seq, Seq+n);//       
    for (i=0; i<n; i++)
		cout<<Seq[i]<<' ';
    cout<<endl;
    return 0;
}