题目描述:
牛牛的作业薄上有一个长度为 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、排列A中的元素是唯一的,即每个数仅出现一次,不存在重复情况;
2、顺序对无关元素绝对位置,只需关注相对位置即可;
3、模糊数不超过10个,对于遍历的负担较小,可以使用穷举。
那么我们需要考虑的就是模糊数所产生的顺序对k2,这个值应是排序A的总顺序对数量k减去已有元素产生的顺序对k1,即k2=k-k1。
另外还需要得到一个存储未使用数字的数组loss、存储模糊数位置的数组indexs。
然后就是将模糊数全排列,这里可以使用递归的方法,传入模糊数组的坐标index、未使用元素的坐标countIndex,与剩余未产生顺序对数量surplus(初始为k2)。
结束条件分为合法输入与非法输入:
合法输入指填充得到的完整排列顺序数与k相同;
非法输入指填充得到的完整排序顺序数与k不同。
使用一个循环将loss数组中的元素依次填入,并递归至下一位置,在填入后需要计算该元素填入该位置后产生的顺序对,计算方法如下(存储数列A的counts以定义为私有变量):
//在index插入count后增加的顺序对
public static int add(int index, int count){
int sum = 0;
for(int i = 0; i < index; i++){
if(counts[i] != 0 && counts[i] < count)
sum++;
}
for(int i = index; i < n; i++){
if(counts[i] != 0 && counts[i] > count)
sum++;
}
return sum;
}
下一次递归的surplus=surplus-add(index,count)。
需要注意的是在递归后需要将该次填充位置的数还原,并将使用的填充数归还。
代码如下:
public static void recur(int index, int countIndex, long surplus){
if(surplus == 0 && loss.size() == 0){
//合法则通过
result++;
return;
}
if(surplus < 0 || countIndex >= loss.size()){
//非法则返回
return;
}
for(int i = 0; i < loss.size(); i++){
int count = loss.remove(i);
//填充
counts[indexs.get(index)] = count;
//下一位置
recur(index+1, countIndex, surplus-add(indexs.get(index), count));
//清除操作
counts[indexs.get(index)] = 0;
loss.add(i, count);
}
}
代码实现:
import java.util.*;
public class Main{
//总数
private static int n;
//总顺序对
private static long k;
//数列
private static int[] counts;
//存储模糊数位置
private static ArrayList<Integer> indexs = new ArrayList<>();
//存储剩余可用数
private static ArrayList<Integer> loss = new ArrayList<>();
//存储数列
private static HashSet<Integer> set = new HashSet<>();
//结果
private static int result;
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
n = sc.nextInt();
k = sc.nextLong();
counts = new int[n];
for(int i = 0; i < n; i++){
counts[i] = sc.nextInt();
}
//分离数列
for(int i = 0; i < n; i++){
set.add(counts[i]);
if(counts[i] == 0){
indexs.add(i);
continue;
}
for(int j = i+1; j < n; j++){
//去除已有顺序对
if(counts[j] > counts[i])
k--;
}
}
//剩余可用数字
for(int i = 1; i <= n; i++){
if(!set.contains(i)){
loss.add(i);
}
}
recur(0, 0, k);
System.out.println(result);
}
}
public static void recur(int index, int countIndex, long surplus){
if(surplus == 0 && loss.size() == 0){
//合法则通过
result++;
return;
}
if(surplus < 0 || countIndex >= loss.size()){
//非法则返回
return;
}
for(int i = 0; i < loss.size(); i++){
int count = loss.remove(i);
//填充
counts[indexs.get(index)] = count;
//下一位置
recur(index+1, countIndex, surplus-add(indexs.get(index), count));
//清除操作
counts[indexs.get(index)] = 0;
loss.add(i, count);
}
}
//在index插入count后增加的顺序对
public static int add(int index, int count){
int sum = 0;
for(int i = 0; i < index; i++){
if(counts[i] != 0 && counts[i] < count)
sum++;
}
for(int i = index; i < n; i++){
if(counts[i] != 0 && counts[i] > count)
sum++;
}
return sum;
}
}