题目
描述
牛牛的作业薄上有一个长度为 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
代码
#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;
}
}