題目描述

Uim成功地按照順序將禮物送到了N個妹子的手里并維持她們的和諧。

Uim現在想知道，他最終選擇的順序是所有給N個妹子送禮順序中、字典序第幾小的。

輸入輸出格式

輸入格式：

第一行一個整數N，表示有N個數。

第二行一個整數X，表示給出的排列。

輸出格式：

一個整數，表示是第幾小的字典序。

輸入輸出樣例

輸入樣例#1：

3
231

輸出樣例#1：

4

說明

1<=N<=9

輸入的排列沒有空格

思路：康托展開模版題

源代碼

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #include<bitset> #define EPS 1e-9 #define PI acos(-1.0) #define INF 0x3f3f3f3f #define LL long long #define Pair pair<int,int> const int MOD = 1E9+7; const int N = 1000+5; const int dx[] = {-1,1,0,0,-1,-1,1,1}; const int dy[] = {0,0,-1,1,-1,1,-1,1}; using namespace std;int fac[N]; char a[N]; void getFactor(int n) { //計算階乘fac[0]=1;for(int i=1; i<=n; i++)fac[i]=fac[i-1]*i; } int contor(int n) { //康托展開int X=0;for(int i=1;i<=n-1;i++){int cnt=0;for(int j=i+1;j<=n;j++)if(a[j]<a[i])cnt++;X+=cnt*fac[n-i];}return X+1; } int main() {int n;scanf("%d",&n);scanf("%s",a+1);getFactor(n);int res=contor(n);printf("%d\n",res);return 0; }

?

總結

以上是生活随笔為你收集整理的Uim的情人节礼物·其之弐（洛谷-P2524）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。