WY13. 数列还原
描述
牛牛的作业薄上有一个长度为 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
C 解法, 执行用时: 1ms, 内存消耗: 380KB, 提交时间: 2020-12-20
#include <stdio.h>
int ct=0;
int check(int x[],int len,int n)
{
int c=0;
for(int i=0;i<len;i++)
for(int j=i+1;j<len;j++)
{
if(x[i]<x[j])
c++;
}
if(c==n)
return(1);
else
return(0);
}
int find(int x[],int f[],int n,int k)
{
for(int i=0;i<n;i++)
{
if(x[i]==0)
{
for(int j=0;j<n;j++)
{
if(f[j]==0)
{
f[j]=1;
x[i]=j+1;
int ff=0;
for(int t=0;t<n;t++)
{
if(f[t]==0)
{
ff=1;
break;
}
}
if(!ff&&check(x, n, k))
{
/*
for(int t=0;t<n;t++)
printf("%d ",x[t]);
printf("\n");*/
ct++;
}
else
find(x,f,n,k);
f[j]=0;
}
}
x[i]=0;
return(1);
}
}
return(0);
}
int main()
{
int n,k;
while(scanf("%d%d",&n,&k)!=EOF)
{
int x[n];
int f[n];
ct=0;
for(int i=0;i<n;i++)
f[i]=0;
for(int i=0;i<n;i++)
{
scanf("%d",&x[i]);
if(x[i]!=0)
{
f[x[i]-1]=1;
}
}
find(x,f,n,k);
printf("%d\n",ct);
}
return(0);
}
C 解法, 执行用时: 2ms, 内存消耗: 232KB, 提交时间: 2018-12-19
#include<stdio.h>
int a[20],tot=0,book[101],n,x[101],res=0,k,i,vis[20];
int getCnt(){
int i,j,res=0;
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
if(x[i]<x[j]) res++;
return res;
}
void dfs(int step){
if(step==n){
if(getCnt()==k) res++;
return;
}
if(x[step]) dfs(step+1);
else
for(int i=0;i<tot;i++)
if(!vis[i]){
vis[i]=1,x[step]=a[i];
dfs(step+1);
vis[i]=0,x[step]=0;
}
}
int main(){
for(scanf("%d%d",&n,&k),i=0;i<n;i++)
scanf("%d",&x[i]),book[x[i]]=1;
for(i=1;i<=n;i++)
if(!book[i]) a[tot++]=i;
dfs(0);
printf("%d\n",res);
}
C 解法, 执行用时: 2ms, 内存消耗: 300KB, 提交时间: 2022-02-04
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int k_cnt = 0;
int order_cnt,n;
int bad_cnt = 0;
int array_raw[100] = {0};
int arr_bad_idx[10] = {0};
int arr_bad_number[10] = {0};
int calculate_reverse_num(int arr[], int length)
{
int i, j;
int reverse_num = 0;
for (i = 0; i < length - 1; i++)
for(j = i+1; j < length; j++)
if (arr[i] < arr[j])
{
reverse_num++;
}
else
{
;
}
return reverse_num;
}
void swap(int *a, int *b)
{
int m;
m = *a;
*a = *b;
*b = m;
}
void perm(int list[], int k, int m)
{
int i;
if(k > m)
{
int array_temp[100];
memcpy(array_temp, array_raw, sizeof(int)*n);
for(i = 0; i < bad_cnt; i++)
array_temp[arr_bad_idx[i]] = list[i];
/*
for(i = 0; i < n; i++)
printf("%d ", array_temp[i]);
printf("\n");
*/
int res = calculate_reverse_num(array_temp, n);
if (order_cnt == res)
k_cnt++;
else
;//printf("res:%d\n",res);
}
else
{
for(i = k; i <= m; i++)
{
swap(&list[k], &list[i]);
perm(list, k + 1, m);
swap(&list[k], &list[i]);
}
}
}
int main()
{
unsigned char array_bitmap[101] = {0};
int i, j;
scanf("%d %d\n", &n, &order_cnt);
//printf("n:%d, k:%d\n", n, order_cnt);
bad_cnt = 0;
for (i = 0; i < n; i++)
{
scanf("%d", array_raw + i);
if (0 == array_raw[i])
{
arr_bad_idx[bad_cnt++] = i;
}
else
{
array_bitmap[array_raw[i]] = 1;
}
}
j = 0;
for (i = 1; i <= n; i++)
{
if (0 == array_bitmap[i])
{
arr_bad_number[j++] = i;
}
else
{
;
}
}
if (j != bad_cnt)
{
printf("err:%d != %d\n", j, bad_cnt);
exit(1);
}
else
{
perm(arr_bad_number, 0, bad_cnt-1);
printf("%d\n", k_cnt);
}
return 0;
}
C 解法, 执行用时: 2ms, 内存消耗: 348KB, 提交时间: 2018-12-18
#include<stdio.h>
int a[20],tot=0,book[100],n,x[100],res=0,k,i,vis[10];
int getCnt(){
int i,j,res=0;
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
if(x[i]<x[j]) res++;
return res;
}
void dfs(int step){
if(step==n){
if(getCnt()==k) res++;
return;
}
if(x[step]) dfs(step+1);
else
for(int i=0;i<tot;i++)
if(!vis[i]){
vis[i]=1,x[step]=a[i];
dfs(step+1);
vis[i]=0,x[step]=0;
}
}
int main(){
for(scanf("%d%d",&n,&k),i=0;i<n;i++)
scanf("%d",&x[i]),book[x[i]]=1;
for(i=1;i<=n;i++)
if(!book[i]) a[tot++]=i;
dfs(0);
printf("%d\n",res);
}
C++14 解法, 执行用时: 2ms, 内存消耗: 352KB, 提交时间: 2018-08-13
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 100 + 3;
int a[maxn]; //存放的原始数据
int b[12]; //存放未知的位置数据
int c[maxn]; //b每个排列放到对应的位置的顺序对
int d[maxn]; //存放已知的位置数据
int n,k;
int below[12][maxn];
int up[12][maxn];
int FindNum(int s[],int len){
int num=0;
for(int i=0;i<len-1;i++){
for(int j=i+1;j<len;j++){
if(s[i]<s[j]){
num++;
}
}
}
return num;
}
int main(){
scanf("%d %d",&n,&k);
int len1=0;
int len2=0;
int vis[maxn];
memset(vis,0,sizeof(vis));
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
vis[a[i]]=1;
c[i]=a[i];
if(a[i]!=0) d[len2++]=a[i];
}
for(int i=1;i<=n;i++){
if(!vis[i]) b[len1++]=i;
}
//预处理，找出比B[i]在第i个位置时，左边比它小的个数，右边比它大的个数
for(int i=0;i<len1;i++){
int num=0,t=0;
for(int j=0;j<n;j++){
if(a[j]!=0){
if(a[j]<b[i]) { ++num;}
}else{
below[t++][b[i]]=num;
}
}
num=0;
t=len1-1;
for(int j=n-1;j>=0;j--){
if(a[j]!=0){
if(a[j]>b[i]) { ++num;}
}else{
up[t--][b[i]]=num;
}
}
}
int ans=0;
int tmp=FindNum(d,len2);
//结果为未知的序列对个数+已知的位置序列对个数+未知的与已知的序列对个数
do {
int sum=tmp;
sum+=FindNum(b,len1);
for(int i=0;i<len1;i++){
sum+=below[i][b[i]]+up[i][b[i]];
}
if(sum==k) ans++;
}while(next_permutation(b,b+len1));
printf("%d\n",ans);
return 0;
}