刷题笔记合集🔗

问题描述

小兰在一座保密大楼里工作。这座大楼有一个特殊的电梯系统，从0楼到达指定楼层m时必须遵循以下规则：

1. 给定一个数字序列，每次可以根据序列中的数字n上升或下降n层
2. 相邻两次移动的方向必须相反
3. 第一次移动必须向上
4. 必须使用序列中的所有数字，可以自行安排使用顺序

请帮助小兰找出能到达目标楼层的序列组合。如果无法到达目标楼层，则输出能到达的最近的较低楼层的序列组合。

输入格式

第一行输入两个整数m和n，分别表示目标楼层和序列长度。 第二行输入n个整数，表示可用的数字序列。

输出格式

输出一个序列，数字间用空格分隔，表示到达目标楼层(或最近较低楼层)的移动序列。

样例输入1

5 3
1 2 6

样例输出1

6 2 1

样例解释

• 使用序列[6,2,1]：
  1. 先上升6层到达6楼
  2. 下降2层到达4楼
  3. 上升1层到达5楼
• [1,2,6]也是可行解，但根据"先处理大值"原则，输出[6,2,1]

数据范围

• 1 ≤ m ≤ 50
• 1 ≤ n ≤ 23
• 序列中每个数的范围：[1,50]

Java 解法

import java.util.*;
import java.util.stream.*;

public class Main {
    // 全局变量：期望选取的上升数个数；允许的上限；记录目前的最佳上升和；记录所有最优路径
    static int expectedCount;              
    static int sumLimit;                   
    static int bestSum = 0;                
    static List<boolean[]> pathList = new ArrayList<>();

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int targetFloor = scanner.nextInt();
        int countNums = scanner.nextInt();
        
        Integer[] arr = new Integer[countNums];
        for (int i = 0; i < countNums; i++) {
            arr[i] = scanner.nextInt();
        }
        System.out.println(calculateResult(targetFloor, countNums, arr));
    }
    
    public static String calculateResult(int targetFloor, int n, Integer[] arr) {
        int totalSum = Arrays.stream(arr).reduce(0, Integer::sum);
        expectedCount = (n + 1) / 2;  // 相当于 n/2 + n%2
        sumLimit = (totalSum + targetFloor) / 2;
        
        // 降序排序，保证先处理较大数值
        Arrays.sort(arr, (a, b) -> b - a);
        
        dfs(arr, 0, new boolean[n], 0, 0);
        
        if (pathList.isEmpty()) {
            return "-1";
        }
        
        // 将所有路径转换为最终序列，并选出最优解（按先大后小的排序规则）
        List<List<Integer>> seqs = pathList.stream()
            .map(path -> buildSequence(path, arr))
            .sorted((s1, s2) -> compareSequences(s1, s2))
            .collect(Collectors.toList());
        
        List<Integer> bestSeq = seqs.get(0);
        return bestSeq.stream().map(String::valueOf).collect(Collectors.joining(" "));
    }
    
    // DFS 递归求所有符合要求的上升序列路径
    public static void dfs(Integer[] arr, int idx, boolean[] path, int currSum, int currCount) {
        if (currCount > expectedCount) return;
        
        if (currCount == expectedCount) {
            if (currSum < bestSum) return;
            if (currSum > bestSum) {
                bestSum = currSum;
                pathList.clear();
            }
            pathList.add(Arrays.copyOf(path, path.length));
            return;
        }
        
        for (int i = idx; i < arr.length; i++) {
            if (currSum + arr[i] > sumLimit) continue;
            path[i] = true;
            dfs(arr, i + 1, path, currSum + arr[i], currCount + 1);
            path[i] = false;
        }
    }
    
    // 根据布尔路径构造最终的序列：上升序列和下降序列交替合并
    public static List<Integer> buildSequence(boolean[] path, Integer[] arr) {
        LinkedList<Integer> upList = new LinkedList<>();
        LinkedList<Integer> downList = new LinkedList<>();
        for (int i = 0; i < arr.length; i++) {
            if (path[i]) upList.add(arr[i]);
            else downList.add(arr[i]);
        }
        List<Inte