蓝桥杯——ALGO998——娜神平衡

通过万岁！！！

题目：给定两个数n、r还有一个数组nums，然后我要求将所有的数分配到两个数组中（数组A和数组B）。但是，这里有几个要求：

第一个数必须给A数组每次只能操作一个数，放入A或者放入B添加完成之后，要保证两个数组和的差距不能超过r。

思路：这个题其实给了一点小小的暗示就是，给定的数特别小，这样我们直接暴力就行了，而且这个题应该就是暴力了。首先定义一个数组vis用来记录目前数在那个数组中（0表示没有使用，1表示在A数组，2表示在B数组）。然后定义两个List，分别是aList和bList，这个就是结果集，因为我们需要不断地对List的尾部进行操作，所以这里使用linkedList。但是需要注意退出的条件，就是vis中的内容都不是0了，这里我们定义了一个flag，来进行判断。技巧：就是暴力，然后逻辑稍微复杂一点。还有就是一些库函数的使用，例如linkedList进行排序。题目链接：http://lx.lanqiao.cn/problem.page?gpid=T2983

java代码

import java.util.Collections;
import java.util.linkedList;
import java.util.Scanner;



public class ALGO998 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int r = scanner.nextInt();
        int[] nums = new int[n];
        // 记录这个位置的数，在哪个数组中
        int[] vis = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }
        linkedList aList = new linkedList<>();
        linkedList bList = new linkedList<>();
        int aSum = 0, bSum = 0;
        getAB(aList, bList, vis, nums, r, aSum, bSum, 0);
        // 排序
        Collections.sort(aList);
        Collections.sort(bList);
        // 输出
        for (Integer a : aList) {
            System.out.print(a + " ");
        }
        System.out.println();
        for (Integer b : bList) {
            System.out.print(b + " ");
        }
    }


    private static int getAB(linkedList aList, linkedList bList, int[] vis, int[] nums, int r,
                             int aSum, int bSum, int flag) {
        if (flag == vis.length) {
            return flag;
        }
        for (int i = 0; i < vis.length; i++) {
            if (vis[i] != 0) {
                continue;
            }
            if (aSum + nums[i] - bSum <= r) {
                // 可以给A数组
                flag++;
                vis[i] = 1;
                aSum += nums[i];
                aList.add(nums[i]);
                flag = getAB(aList, bList, vis, nums, r, aSum, bSum, flag);
                if (flag == vis.length) {
                    return flag;
                }
                aList.removeLast();
                aSum -= nums[i];
                vis[i] = 0;
                flag--;
            }
            if (bSum + nums[i] - aSum <= r) {
                // 给B数组的不能是第一个元素
                if (i == 0) {
                    continue;
                }
                // 给B数组
                flag++;
                vis[i] = 2;
                bSum += nums[i];
                bList.add(nums[i]);
                flag = getAB(aList, bList, vis, nums, r, aSum, bSum, flag);
                if (flag == vis.length) {
                    return flag;
                }
                bList.removeLast();
                bSum -= nums[i];
                vis[i] = 0;
                flag--;
            }
        }
        return flag;
    }
}

总结：题目就是暴力，需要注意的是递归和退出递归的条件。还有就是我们使用的数据结构是linkedList，以及使用Collections.sort对其进行排序。