【蓝桥备赛】数字王国之军训排队—

【蓝桥备赛】数字王国之军训排队——DFS深度优先搜索

本文主要是介绍【蓝桥备赛】数字王国之军训排队——DFS深度优先搜索，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

数字王国之军训排队

个人思路

一般最坏情况，就是这几个数都存在倍数关系，那么就是 n 个数分成 n 个队。然后本题 n 的范围不大，可以枚举 1 ~ n 得到，如果数字范围大可以考虑进行二分。从 1 ~ n ,第一次满足条件的队伍数，即答案，输出即可。
对于每一种队伍情况，使用dfs遍历每个数可以存放的队列，如果当前队列存在能被整除的数，则换下一个队；如果能放入当前队，则继续看下一个数。
先放入大的数，再放入小的数，肯定较小的数除以较大的数无法整除，所以需要先对数组排序。

	for(int i = 1; i <= team; ++i){int flag = 1;for(const auto j : record[i]){if(arr[x] % j == 0){flag = 0;break;} }if(flag){record[i].push_back(arr[x]);if(dfs(x + 1, team))return true;record[i].pop_back();}}

参考代码

Java

import java.io.*;
import java.util.*;public class Main {static int n;static int[] arr;static List<Integer>[] record;static boolean dfs(int now, int team) {if (now == n) return true;for (int i = 0; i < team; i++) {List<Integer> list = record[i];boolean flag = true;for (int j : list) {if (arr[now] % j == 0) {flag = false;break;}}if (flag) {list.add(arr[now]);if (dfs(now + 1, team)) {return true;}list.remove(list.size() - 1);}}return false;}public static void main(String[] args) {Scanner sc = new Scanner();n = sc.nextInt();record = new ArrayList[n];for (int i = 0; i < n; i++) {record[i] = new ArrayList<>();}arr = new int[n];for (int i = 0; i < n; i++) {arr[i] = sc.nextInt();}Arrays.sort(arr);for (int i = 1; i <= n; ++i) {if (dfs(0, i)) {System.out.println(i);break;}}}
}
class Scanner {static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));public int nextInt() {try {st.nextToken();} catch (IOException e) {throw new RuntimeException(e);}return (int) st.nval;}
}

C/C++

#include<bits/stdc++.h>
using namespace std;
const int N = 15;
int n, arr[N];
vector<int> record[N];int dfs(int x, int team)
{if(x == n + 1)return true;for(int i = 1; i <= team; ++i){int flag = 1;for(const auto j : record[i]){if(arr[x] % j == 0){flag = 0;break;} }if(flag){record[i].push_back(arr[x]);if(dfs(x + 1, team))return true;record[i].pop_back();}}return false;
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n;for(int i = 1; i <= n; ++i) cin >> arr[i];sort(arr + 1, arr + 1 + n);for(int i = 1; i <= n; ++i){if(dfs(1, i)) {cout << i;return 0;}}
}