栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

蓝桥杯 java 娜神平衡

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

蓝桥杯 java 娜神平衡

算法:

使用到的算法是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分,估摸着应该是有大数,毕竟本质还是递归且暴力枚举。

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/770628.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号