数列还原

题目描述

牛牛的作业薄上有一个长度为 n 的排列 A，这个排列包含了从1到n的n个数，但是因为一些原因，其中有一些位置（不超过 10 个）看不清了，但是牛牛记得这个数列顺序对的数量是 k，顺序对是指满足 i < j 且 A[i] < A[j] 的对数，请帮助牛牛计算出，符合这个要求的合法排列的数目。

输入描述:

每个输入包含一个测试用例。每个测试用例的第一行包含两个整数 n 和 k（1 <= n <= 100, 0 <= k <= 1000000000），接下来的 1 行，包含 n 个数字表示排列 A，其中等于0的项表示看不清的位置（不超过 10 个）。

输出描述:

输出一行表示合法的排列数目。

示例1

输入

5 5
4 0 0 2 0

输出

2

思路：
1.因为往数组里插入一个数，不会影响到原来的顺序对，插入一个数后，新的顺序对=原顺序对+由于插入产生的顺序对。
2.总顺序对=给定数的顺序对+未给定数的顺序对+混合时产生的顺序对。
3.未给定的数可以有各种排列，所以要求出他的全排列，以及每一种情况对应混合时产生的顺序对。

题解：

#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;
        }
    }
    //计算给定数组的顺序对
    int given = getOrderPair(arr, n);
    if(given>k){
        printf("%d", 0);
    }
    
    //计算未给定数据排在每个缺失的位置上产生的顺序对
    //每个缺失的数
    for(int i=0;i<cnt;i++){
        //每个缺失的位置
        for(int j=0;j<cnt;j++){
            //遍历数组
            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;
    //计算对于未给定的数的全排列所产生的顺序对
    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;
}