蓝桥杯刷题记录之数字王国之军训排队

记录

卡了半天，check函数中的temp % ele ==0写成了ele % temp == 0就挺无语的

思路

这个晚上在补

代码

import java.util.*;
public class Main{
    static List<List<Integer>> que = new ArrayList<>();
    static int MIN = Integer.MAX_VALUE;
    static int[] people;
    public static void dfs(int index){
        if(index==people.length)
        {
            MIN = Math.min(MIN,que.size());
            return;
        }
        if(index>=MIN)
            return;
        int temp = people[index];
        for(int i=0;i<que.size();i++){
            //能加入队伍
            List<Integer> list = que.get(i);
                if(check(list,temp)){
                    list.add(temp);
                    dfs(index+1);
                    list.remove(list.size()-1);

                }
        }
        // 自立门户
        List<Integer> item =new LinkedList<>();
        item.add(temp);
        que.add(item);
        dfs(index+1);
        que.remove(que.size()-1);

    }

    private static boolean check(List<Integer> list, int temp) {
        for(Integer ele: list){
            if(temp % ele ==0)
                return false;
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        people = new int[n];
        for(int i=0;i<n;i++){
            people[i] = s.nextInt();
        }
        Arrays.sort(people);
        List<Integer> item = new LinkedList<>();
        item.add(people[0]);
        que.add(item);
        dfs(1);
        System.out.println(MIN);
        s.close();
    }
}