題目描述
牛牛的作業(yè)薄上有一個長度為 n 的排列 A损俭，這個排列包含了從1到n的n個數(shù)数焊，但是因為一些原因疯搅，其中有一些位置（不超過 10 個）看不清了，但是牛牛記得這個數(shù)列順序?qū)Φ臄?shù)量是 k健爬，順序?qū)κ侵笣M足 i < j 且 A[i] < A[j] 的對數(shù)，請幫助牛牛計算出么介，符合這個要求的合法排列的數(shù)目娜遵。
輸入描述:
每個輸入包含一個測試用例。每個測試用例的第一行包含兩個整數(shù) n 和 k（1 <= n <= 100, 0 <= k <= 1000000000）壤短，接下來的 1 行设拟，包含 n 個數(shù)字表示排列 A慨仿，其中等于0的項表示看不清的位置（不超過 10 個）。
輸出描述:
輸出一行表示合法的排列數(shù)目纳胧。
示例1
輸入
5 5
4 0 0 2 0
輸出
2
思路：
1.因為往數(shù)組里插入一個數(shù)镰吆，不會影響到原來的順序?qū)Γ迦胍粋€數(shù)后跑慕，新的順序?qū)?原順序?qū)?由于插入產(chǎn)生的順序?qū)Α?br>
2.總順序?qū)?給定數(shù)的順序?qū)?未給定數(shù)的順序?qū)?混合時產(chǎn)生的順序?qū)Α?br>
3.未給定的數(shù)可以有各種排列万皿，所以要求出他的全排列，以及每一種情況對應(yīng)混合時產(chǎn)生的順序?qū)Α?/p>
題解：
#include<cstdio>
#include<algorithm>
using namespace std;
int n;
long long k;
int arr[110];
int num[110];
int missidx[11];
int missnum[11];
int order[110][110];
int getOrderPair(int arr[], int n){
int cnt=0;
for(int i=0;i<n;i++){
if(arr[i] == 0) continue;
for(int j=i+1;j<n;j++){
if(arr[j]==0) continue;
if(arr[i]<arr[j]) cnt++;
}
}
return cnt;
}
int main(){
scanf("%d %lld", &n, &k);
int cnt=0;
for(int i=0;i<n;i++){
scanf("%d", &arr[i]);
if(arr[i] == 0){
missidx[cnt++]=i;
}else{
num[arr[i]] = 1;
}
}
cnt=0;
for(int i=1;i<=n;i++){
if(num[i]==0){
missnum[cnt++]=i;
}
}
//計算給定數(shù)組的順序?qū)? int given = getOrderPair(arr, n);
if(given>k){
printf("%d", 0);
}
//計算未給定數(shù)據(jù)排在每個缺失的位置上產(chǎn)生的順序?qū)? //每個缺失的數(shù)
for(int i=0;i<cnt;i++){
//每個缺失的位置
for(int j=0;j<cnt;j++){
//遍歷數(shù)組
for(int r=0;r<n;r++){
if(arr[r] == 0) continue;
if(r < missidx[j] && arr[r] < missnum[i]) order[missidx[j]][missnum[i]]++;
if(r > missidx[j] && arr[r] > missnum[i]) order[missidx[j]][missnum[i]]++;
}
}
}
int ans = 0;
//計算對于未給定的數(shù)的全排列所產(chǎn)生的順序?qū)? do{
int notGiven = getOrderPair(missnum, cnt);
for(int i=0;i<cnt;i++){
notGiven += order[missidx[i]][missnum[i]];
}
if(given + notGiven == k){
ans++;
}
}while(next_permutation(missnum, missnum+cnt));
printf("%d", ans);
return 0;
}
