算法:
使用到的算法是dfs(深搜)+回溯。这里不讲算法原理,可以自己去找材料看一下,花点时间即可。
伪代码:(不一定全,只做思想参考)
dfs(step =1){
if(基本情况:A数组有a[o],并且step>a.length)
sout(输出数组)
} for(a数组的元素集){
if(看看当前元素有没有被用,用b[i]来标记)
b[i] = 1;//没用就直接用。最后还是要回溯,回溯就不写了。
if(如果能放左结点,也就是A数组){
//结点操作,既然能放,就直接放
A[i]= a[i]
dfs(step+1,递归)
//回溯
//不回溯,递归返回到前面就没机会了
A[i] = 0;
}
if(左节点不能放,就看看右边能不能放,也就是B数组){
//结点操作,既然能放,就直接放
B[i]= a[i]
dfs(step+1,递归)
//回溯
//不回溯,递归返回到前面就没机会了
B[i] = 0;
}
程序思路:
通过dfs,把所有的数都遍历一边,每一次都判断是否满足小于10(看试卷给)来决定是否递归。最后再将a,b两个数组排序并且输出结果即可
代码如下:
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static boolean one = true;
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int step = 1;
int an = input.nextInt();
int m = input.nextInt();
int[] a = new int[an];
for (int i = 0; i < an; i++) {
a[i] = input.nextInt();
}
int[] b = new int[an];//和a一样,不过全是0,用来标记a的每个元素的使用情况。
int[] A = new int[an];
int[] B = new int[an];
// int[] sums;
new Main().backtracing(step,a,b,A,B,m);
}
public void backtracing(int step,int[]a,int[]b,int[]A,int[]B,int m){
//dfs
if(step>a.length&&findFist(a[0],A)&&one) {//边界
//只循环一次,因为放的顺序不同,但是最后结果相同,没必要,得到一次结果就行,并且程序会保证是唯一的结果。
one = false;
//调用函数,把AB排序和去零处理
check(A);
System.out.println();
check(B);
}
for(int i =0; i
结果:运行超时,80分,估摸着应该是有大数,毕竟本质还是递归且暴力枚举。



