【蓝桥备赛】数字王国之军训排队——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();
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

参考代码

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

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;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48