【算法】粘木棍问题（C/C++）

搜索算法介绍

DFS:

深度优先搜索（Depth-First Search，简称DFS）是一种用于遍历或搜索树或图的算法。这种算法会尽可能深地搜索图的分支，直到找到目标节点或达到叶节点（没有子节点的节点），然后回溯到上一个分支继续搜索。DFS可以用于许多问题，比如路径寻找、连通性验证、拓扑排序等。

在ACM、蓝桥杯等著名竞赛中DFS算法是比较重要的，特别是在蓝桥杯中每一年几乎都要考DFS/BFS算法。DFS算法在OI赛中用处非常大，可以通过DFS/BFS暴力的方式可以拿到部分分数，蓝桥杯一般可以拿到20%的分数，有的甚至高达50%，是暴力得分的不二之选。

基本步骤：

DFS通常使用递归或栈来实现。以下是DFS的基本步骤：

选择起始点：选择图中的一个点作为起始点。

访问节点：标记起始节点为已访问，并将该节点加入递归或栈中。

探索邻接节点：从该点周围取出一个点，检查它的所有未访问的邻接节点。

递归或迭代：对每个未访问的邻接节点，将其标记为已访问，然后将其推入递归或栈中。

回溯：当当前节点的所有邻接节点都被访问后，递归中回溯/从栈中弹出该节点，继续搜索上一个点的其他分支。

结束条件：当栈为空或找到目标节点时，搜索结束。

BFS：

广度优先搜索（Breadth-First Search，简称BFS） 是一种遍历或搜索树和图的算法，也称为宽度优先搜索，BFS算法从图的某个节点开始，依次对其所有相邻节点进行探索和遍历，然后再对这些相邻节点的相邻节点进行探索，直到遍历完所有的节点。BFS算法使用队列来辅助实现，将起始节点放入队列中，然后依次取出队列中的节点，访问其相邻节点，并将其加入队列。这样可以保证从起始节点出发，依次按照距离顺序遍历节点。BFS常用于寻找最短路径，因为它按照从起点到每个节点的距离来探索节点。

在ACM、蓝桥杯等著名竞赛中BFS算法是比较重要的，特别是在蓝桥杯中每一年几乎都要考DFS/BFS算法。BFS算法在OI赛中用处非常大，可以通过DFS/BFS暴力的方式可以拿到部分分数，蓝桥杯一般可以拿到20%的分数，有的甚至高达50%，是暴力得分的不二之选。

基本步骤：

BFS算法通常使用队列来实现，BFS算法的具体步骤如下：

创建一个队列，将起始节点加入队列；

创建一个集合，用于存储已经访问过的节点；

从队列中取出一个节点，并将其标记为已访问；

访问该节点的所有相邻节点，如果相邻节点未被访问，则将其加入队列；

重复步骤3和步骤4，直到队列为空。

BFS算法可以用来解决一些问题，例如图的遍历、最短路径搜索等。由于BFS算法保证了按照距离顺序遍历节点，因此可以用来寻找最短路径。另外，BFS算法还可以用来判断图是否连通，即从一个节点是否可以到达另一个节点。

动图算法

红色遍历为BFS宽度优先搜索，黄色为DFS深度优先搜索，绿色为起点，紫色为终点，黑色为障碍物）。

粘木棍问题

问题描述

　　有N根木棍，需要将其粘贴成M个长木棍，使得最长的和最短的的差距最小。

输入格式

　　第一行两个整数N,M。

　　一行N个整数，表示木棍的长度。

输出格式

　　一行一个整数，表示最小的差距

样例输入

3 2

10 20 40

样例输出

10

数据规模和约定

　　N, M<=7

题目链接：“蓝桥杯”练习系统

思路一：

此题给出的知识标签是搜索，那就想dfs，不断尝试两个数据合并一个数据，当到达m个数据时，寻找此时最大最小值，做差，然后回溯，换两个数据合并，到达m个数，再回溯…… 直到所有情况合并完，对于这个题来说，n,m都小于等于7，这样做完全没问题，但是时间复杂度比较大，盲目搜索，有一些不必要的合并，这种方法不太推荐，写一下代码，交上也可以过。

#include<iostream>
using namespace std;
int n,m;
int a[10];
int sum=0x3f3f;
void dfs(int k) {
  if(k==m) {
    int maxx=0;
    int minx=0x3f3f;
    for(int i=0; i<m; i++) {
      minx=min(minx,a[i]);
      maxx=max(maxx,a[i]);
    }
    sum=min(maxx-minx,sum);
    return;
  }
  for(int i=0; i<k; i++) {
    for(int j=i+1; j<k; j++) {
      a[i]+=a[j];
      int tmp=a[j];
      a[j]=a[k-1];
      a[k-1]=tmp;
      dfs(k-1);
      tmp=a[j];
      a[j]=a[k-1];
      a[k-1]=tmp;
      a[i]-=a[j];
    }
  }
}
int main() {
  cin>>n>>m;
  for(int i=0; i<n; i++) {
    cin>>a[i];
  }
  dfs(n);
  cout<<sum<<endl;
  return 0;
}

思路二：

思路二就有点贪心的思想了，我们可以简化为一个模型，有n个数，m个箱子，不断往里面放数，每放一个数就要遍历一遍寻找最小值的箱子，然后把数放进去，直到放完为止，越往后的数，数越小（前提由大到小排好序），这样也就达到了我们寻找最小差值的目的。首先我们先初始化m个箱子的初始值，我们要选n个数中前m大的数，作为m个箱子的初始值，为什么选前m大的值，因为我们要求最小差值，先放完最大值，剩下小的，不断往里面补，使得减小差值的目的，比如样例，10 20 40，先选，20，40作为箱子，遍历一遍寻找最小值20，把10放进去，更新为30，数都放完了，此时最小差值10。如果前m小的数作为箱子，10，20，寻找最小值10，把40放进去，更新为50，最小差值为20。这样保证了每次更新都是有用的更新，大大降低了时间复杂度。话不多说，上代码。

#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
int a[10],b[10];
int cmd(int A,int B){
  return A>B;
}
int main(){
  cin>>n>>m;
  for(int i=0;i<n;i++){
    cin>>a[i];
  }
  sort(a,a+n,cmd);//由大到小排序
  for(int i=m;i<n;i++){//遍历除去前m大的数，往里面添加
    int index=0;
    int minx=0x3f3f3f;
    for(int j=0;j<m;j++){//选取前m大的数相当于箱子，哪个数小，就往里放
      if(a[j]<minx){//寻找此时前m大的数最小值
        index=j；//记录下标
        minx=a[j];//更新值
      }
    }
    a[index]+=a[i];//找到最小的值（箱子），把此时未放进去的数，加上
  }
  int maxx=0;
  int minx=0x3f3f3f;
  for(int i=0;i<m;i++){//寻找此时最大最小值，做差
    maxx=max(maxx,a[i]);
    minx=min(minx,a[i]);
  }
  cout<<maxx-minx<<endl;
  return 0;
}

以上为搜索算法思路总结，此题比较简单，属于小白签到题，愿与大家共同进步。执笔至此，感触彼多，全文将至，落笔为终，感谢大家的支持。