南郵-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
テーマソース
アルゴリズム設計と実験問題解
コード:
時間制限(通常/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;
}