题目描述

有一座保密大楼，你从0楼到达指定楼层m，必须这样的规则乘坐电梯：

给定一个数字序列，每次根据序列中的数字n，上升n层或者下降n层，前后两次的方向必须相反，规定首次的方向向上，自行组织序列的顺序按规定操作到达指定楼层。

求解到达楼层的序列组合，如果不能到达楼层，给出小于该楼层的最近序列组合。

输入描述

第一行：期望的楼层，取值范围[1,50]; 序列总个数，取值范围[1,23]

第二行：序列，每个值取值范围[1,50]

输出描述

能够达到楼层或者小于该楼层最近的序列

备注

• 操作电梯时不限定楼层范围。
• 必须对序列中的每个项进行操作，不能只使用一部分。

用例1

输入

5 3
1 2 6

输出

6 2 1

说明

1 2 6，6 2 1均为可行解，按先处理大值的原则结果为6 2 1

参考题库

华为OD机试真题目录

解答代码

思路递归回溯

#include<iostream>
#include<vector>
#include<string>
#include <utility> 
#include <sstream>
#include<algorithm>
#include<list>
#include<queue>
#include<map>
#include<set>
using namespace std;

bool cmp(int x, int y) {
    return x > y;
}
// 整体序列和
int totalSum;
vector<int> res;
int minDiff;
int m,n;

// 递归回溯枚举 选取exceptCount的数
void DFS(vector<int>& ans, int index , int currentSum, int count, int exceptCount, int& visited) {
    if (count > exceptCount) {
        return;
    }
    if (exceptCount == count) {
        // 净增楼层
        int diff = currentSum - (totalSum - currentSum);
       // 上升超过m的不考虑
       if (diff > m) {
          return;
       }
       
       // 找最小差距
       diff = abs(diff - m);
       if (diff < minDiff) {
           res.clear();
           minDiff = diff;
           res.push_back(visited);   
       } else if (diff == minDiff) {
          res.push_back(visited);
       }
       return;
    }

    for (int i = index; i < n; i++) {
        int num = ans[i];
        int nextCurrentSum = currentSum + num;
        // 剪枝 最终会超过m层
        if (nextCurrentSum - (totalSum - nextCurrentSum) > m) {
            continue;
        }
        // 递归回溯
        visited |= 1 << (n - i -1);
        DFS(ans, i + 1, nextCurrentSum, count + 1, exceptCount, visited);
        visited &= ~(1 << (n - i - 1));

    }
}

// 交叉构建结果集
vector<int> buildArr(vector<int>& ans, int num) {
    vector<bool> visted(n, false);
    for (int i = 0; i < n; i++) {
        visted[i] = 1 & (num >> (n-1-i));
    }
    vector<int> s(n);
    int pos = 0;
    for (int i = 0; i < n; i++) {
        if (visted[i]) {
            s[pos] = ans[i];
            pos += 2; 
        }       
    }
    pos = 1;
    for (int i = 0; i < n; i++) {
        if (!visted[i]) {
            s[pos] = ans[i];
            pos += 2; 
        }       
    }
    return s;
}

// 在所有mask生成的数组中，找出字典序最大的
vector<int> findBestArray(vector<int>& ans) {
    vector<int> best;

    for (const int& mask : res) {
        vector<int> curr = buildArr(ans, mask);
        if (best.empty() || curr > best) {
            best = curr;
        }
    }
    return best;
}

int main() {
    cin >> m >> n;
    vector<int> ans(n);
    int sum = 0;
    for (int i = 0; i < n; i++) {
        cin >> ans[i];
        sum += ans[i];
    }
    
    totalSum = sum;
    minDiff = sum + m;
    // 从大到小排序
    sort(ans.begin(), ans.end(), cmp);
    // 向上取整 向上的数量
    int exceptUpCount = (n + 1) / 2;

    int status = 0;
    DFS(ans, 0, 0, 0, exceptUpCount, status);

    vector<int>anwser =  findBestArray(ans);
    for (int i = 0; i < n; i++) {
        cout << anwser[i];
        if (i != n-1) {
            cout << " ";
        }
    }
    return 0;
}