牛客-数列还原

发表于 | 分类于 ，

题目

描述

牛牛的作业薄上有一个长度为 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 个）。

输出

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

Example

Input

5 5
4 0 0 2 0

Output

2

题解

思路

  • 计算已有序列的顺序对数 extPairs,
  • 对于看不清的数字,进行全排列,
  • 对于每一种全排列,
    • 计算此序列的顺序对数 newPairs
    • 计算添加新的数字之后,已知序列增加的顺序对数 addPairs
    • 若 extPairs+newPairs+addPairs==k 则合法排列数目 +1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>

#define ll long long

using namespace std;

int n,k,m,o,arr[100],add[100],pos[100],i,j,t,p,c;

ll countPairs(int* a,int n)
{
    ll t=0;
    for(int i=0;i<n;++i)
        for(int j=0;j<i;++j)
            if(a[j]<a[i])
                ++t;
    return t;
}

ll countPairs()
{
    ll t=0;
    for(int i=0;i<o;++i)
    {
        for(int j=0;j<pos[i];++j)
            if(arr[j]<add[i])
                ++t;
        for(int j=pos[i];j<m;++j)
            if(arr[j]>add[i])
                ++t;
    }
    return t;
}

int main(int argc, const char * argv[])
{
    ll extPair,newPair,addPair;
    bool flag[101];
    while(cin>>n>>k)
    {
        memset(flag,0,sizeof flag);
        c=p=0;
        for(i=m=o=0;i<n;++i)
        {
            cin>>t;
            if(t)
            {
                arr[m++]=t;
                flag[t]=1;
                p=m;
            }
            else
            {
                pos[o++]=p;
            }
        }
        for(i=1,j=0;i<=n;++i)
        {
            if(!flag[i])
            {
                add[j++]=i;
            }
        }
        extPair=countPairs(arr,m);
        do
        {
            newPair=countPairs(add,o);
            addPair=countPairs();
            if(extPair+newPair+addPair==k)
                ++c;
        }
        while(next_permutation(add,add+o));
        cout<<c<<endl;
    }
}