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

2024-01-31 00:44

本文主要是介绍【蓝桥备赛】数字王国之军训排队——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;}}
}

这篇关于【蓝桥备赛】数字王国之军训排队——DFS深度优先搜索的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/662075

相关文章

深度解析Java DTO(最新推荐)

《深度解析JavaDTO(最新推荐)》DTO(DataTransferObject)是一种用于在不同层(如Controller层、Service层)之间传输数据的对象设计模式,其核心目的是封装数据,... 目录一、什么是DTO?DTO的核心特点:二、为什么需要DTO?(对比Entity)三、实际应用场景解析

深度解析Java项目中包和包之间的联系

《深度解析Java项目中包和包之间的联系》文章浏览阅读850次,点赞13次,收藏8次。本文详细介绍了Java分层架构中的几个关键包:DTO、Controller、Service和Mapper。_jav... 目录前言一、各大包1.DTO1.1、DTO的核心用途1.2. DTO与实体类(Entity)的区别1

深度解析Python装饰器常见用法与进阶技巧

《深度解析Python装饰器常见用法与进阶技巧》Python装饰器(Decorator)是提升代码可读性与复用性的强大工具,本文将深入解析Python装饰器的原理,常见用法,进阶技巧与最佳实践,希望可... 目录装饰器的基本原理函数装饰器的常见用法带参数的装饰器类装饰器与方法装饰器装饰器的嵌套与组合进阶技巧

深度解析Spring Boot拦截器Interceptor与过滤器Filter的区别与实战指南

《深度解析SpringBoot拦截器Interceptor与过滤器Filter的区别与实战指南》本文深度解析SpringBoot中拦截器与过滤器的区别,涵盖执行顺序、依赖关系、异常处理等核心差异,并... 目录Spring Boot拦截器(Interceptor)与过滤器(Filter)深度解析:区别、实现

深度解析Spring AOP @Aspect 原理、实战与最佳实践教程

《深度解析SpringAOP@Aspect原理、实战与最佳实践教程》文章系统讲解了SpringAOP核心概念、实现方式及原理,涵盖横切关注点分离、代理机制(JDK/CGLIB)、切入点类型、性能... 目录1. @ASPect 核心概念1.1 AOP 编程范式1.2 @Aspect 关键特性2. 完整代码实

SpringBoot开发中十大常见陷阱深度解析与避坑指南

《SpringBoot开发中十大常见陷阱深度解析与避坑指南》在SpringBoot的开发过程中,即使是经验丰富的开发者也难免会遇到各种棘手的问题,本文将针对SpringBoot开发中十大常见的“坑... 目录引言一、配置总出错?是不是同时用了.properties和.yml?二、换个位置配置就失效?搞清楚加

HTML5 搜索框Search Box详解

《HTML5搜索框SearchBox详解》HTML5的搜索框是一个强大的工具,能够有效提升用户体验,通过结合自动补全功能和适当的样式,可以创建出既美观又实用的搜索界面,这篇文章给大家介绍HTML5... html5 搜索框(Search Box)详解搜索框是一个用于输入查询内容的控件,通常用于网站或应用程

Python中文件读取操作漏洞深度解析与防护指南

《Python中文件读取操作漏洞深度解析与防护指南》在Web应用开发中,文件操作是最基础也最危险的功能之一,这篇文章将全面剖析Python环境中常见的文件读取漏洞类型,成因及防护方案,感兴趣的小伙伴可... 目录引言一、静态资源处理中的路径穿越漏洞1.1 典型漏洞场景1.2 os.path.join()的陷

Spring Boot拦截器Interceptor与过滤器Filter深度解析(区别、实现与实战指南)

《SpringBoot拦截器Interceptor与过滤器Filter深度解析(区别、实现与实战指南)》:本文主要介绍SpringBoot拦截器Interceptor与过滤器Filter深度解析... 目录Spring Boot拦截器(Interceptor)与过滤器(Filter)深度解析:区别、实现与实

MyBatis分页插件PageHelper深度解析与实践指南

《MyBatis分页插件PageHelper深度解析与实践指南》在数据库操作中,分页查询是最常见的需求之一,传统的分页方式通常有两种内存分页和SQL分页,MyBatis作为优秀的ORM框架,本身并未提... 目录1. 为什么需要分页插件?2. PageHelper简介3. PageHelper集成与配置3.