蓝桥杯-粘木棍-DFS

题目

思路

--有n根木棍，需要将其粘成m根木棍，并求出最小差值，可以用DFS枚举出所有情况。粘之前有n根短木棍，粘之后有m根长木棍，那么让长木棍的初始长度设为0。外循环让所有的短木棍都参与粘，内循环让要粘的短木棍选择某个长木棍。再结合DFS进行n层递归，每层都粘一个短木棍，并且下一层要将已经粘过的排除掉。

--递归时最好不要用sort排序，很有可能会影响其他层的递归。

代码

#include <iostream>
#include <cmath>
using namespace std;

int a[7];
int b[7] = {0}; //长木棍，由短木棍拼接而成，拼接前长度设为0 
bool v[7] = {false};
int n, m;
int mincha = 30000; //便于求出最小的差值

void dfs(int s){
    if (s == n){
        int minb, maxb;
        minb = maxb = b[0];
        for (int i = 0; i < m; i++){
            minb = min(minb, b[i]);
            maxb = max(maxb, b[i]);
        }
        int cha = maxb - minb;
        mincha = min(mincha, cha); //更新mincha
        return;
    }
    else{
        for (int i = s; i < n; i++){
            for (int j = 0; j < m; j++){
                if (v[i] == false){ //标记短木棍是否已被分配给长木棍 
                    v[i] = true;
                    b[j] += a[i];
                    dfs(s + 1);
                    v[i] = false;
                    b[j] -= a[i];
                } 
            }
        } //外层循环是短木棍，内层是长木棍，让每根短的都有机会粘到长的上面，枚举出所有可能的况。 
    }
}

int main(){
    cin >> n >> m;
    for (int i = 0; i < n; i++){
        cin >> a[i];
    }
    dfs(0);
    cout << mincha << endl;
    
    return 0;
}
/*
    不能对数组b用sort排序，会改变b的顺序。单看改变b的顺序对这层递归没有什么影响，但是对其它层的递归有影响。 
*/