P10377 [GESP202403 六级] 好斗的牛

记录119#includebits/stdc.h using namespace std; const int MAXN15; int n,a[MAXN],b[MAXN],order[MAXN]; // n为牛的数量a[i], b[i]存第i头牛的左右攻击范围order数组记录当前排列中第step头牛的编号 bool vis[MAXN];// 标记数组vis[i]1表示第i头牛已经被放入排列中 int min_len1e9;// 记录最少需要的牛棚数量初始化为一个很大的数 void dfs(int step){ // step表示当前正在放置第几头牛从1开始 if(stepn){// 递归边界如果 n 头牛全部放置完毕 int cur_len1;// 当前排列需要的总长度初始为1因为第一头牛自己至少占1个牛棚 for(int i2;in;i){// 从第2头牛开始依次计算它与上一头牛的间隔及自身占位 int last_coworder[i-1];// 获取上一头牛的编号 int cur_coworder[i];// 获取当前这头牛的编号 cur_lenmax(a[cur_cow],b[last_cow])1; // 累加长度中间需要的空牛棚数(max(当前牛的左范围, 上一头牛的右范围)) 当前牛自己占的1个牛棚 } min_lenmin(min_len,cur_len);// 用当前排列算出的长度更新全局最小值 return; // 结束本次递归返回上一层 } for(int i1;in;i){// 尝试把每一头牛编号1到n放在当前的 step 位置 if(vis[i]0){ // 如果第 i 头牛还没有被使用过 vis[i]1; // 标记第 i 头牛已使用 order[step]i;// 记录当前第 step 个位置放的是第 i 头牛 dfs(step1);// 递归调用去放置下一头牛第 step1 头 vis[i]0; // 回溯取消第 i 头牛的标记以便在后续循环中尝试其他排列 } } } int main(){ ios::sync_with_stdio(false); cin.tie(0); cinn; for(int i1;in;i) cina[i]; for(int i1;in;i) cinb[i]; dfs(1); coutmin_len; return 0;//结束程序 }前言我是一名专注信奥赛CSP-J/S、NOIP的教练。如果你觉得这篇题解对你有帮助欢迎点击关注我的CSDN账号我会持续更新高质量算法解析。我深知算法思维的构建远比单纯通过题目更重要本系列题解不局限于AC代码的堆砌而是致力于拆解题目背后的逻辑链条与核心知识点备赛路上若遇瓶颈欢迎随时评论或私信我将甄选典型疑难问题通过视频讲解或撰写专项文章的形式为你提供深度答疑。题目传送门https://www.luogu.com.cn/problem/P10377思路1. 题意理解与数学建模攻击范围转化为安全距离两头相邻的牛假设左边是last_cow右边是cur_cow要和平共处它们之间的空牛棚数量必须同时满足两者的要求。即空牛棚数 ≥≥b[last_cow]且 空牛棚数 ≥≥a[cur_cow]。因此它们之间最少需要的空牛棚数为max(b[last_cow], a[cur_cow])。总长度计算如果确定了牛的排列顺序第一头牛占据 1 个牛棚之后每放入一头新牛都需要增加“安全间隔”加上“自身占位1个牛棚”。2. 算法选择全排列枚举由于 n≤9n≤9 最多有 9!362880种排列方式。这个数据规模非常小完全可以通过暴力搜索DFS枚举所有可能的排列组合。对于每一种合法的排列计算出所需的总牛棚数最后取所有方案中的最小值即可。代码解析#includebits/stdc.h using namespace std; const int MAXN15; int n, a[MAXN], b[MAXN], order[MAXN]; // n为牛的数量a[i], b[i]存第i头牛的左右攻击范围order数组记录当前排列中第step头牛的编号 bool vis[MAXN]; // 标记数组vis[i]1表示第i头牛已经被放入排列中 int min_len1e9; // 记录最少需要的牛棚数量初始化为一个很大的数INF解析定义了全局变量和常量。order数组用于保存当前 DFS 路径上的牛的排列顺序vis数组用于防止同一头牛在一次排列中被重复使用。void dfs(int step){ // step表示当前正在放置第几头牛从1开始 if(step n){ // 递归边界如果 n 头牛全部放置完毕 int cur_len 1; // 当前排列需要的总长度初始为1因为第一头牛自己至少占1个牛棚 for(int i 2; i n; i){ // 从第2头牛开始依次计算它与上一头牛的间隔及自身占位 int last_cow order[i-1]; // 获取上一头牛的编号 int cur_cow order[i]; // 获取当前这头牛的编号 cur_len max(a[cur_cow], b[last_cow]) 1; // 累加长度中间需要的空牛棚数(max(当前牛的左范围, 上一头牛的右范围)) 当前牛自己占的1个牛棚 } min_len min(min_len, cur_len); // 用当前排列算出的长度更新全局最小值 return; // 结束本次递归返回上一层 }解析这是 DFS 的核心部分。当step n时说明已经成功生成了一个包含 nn 头牛的完整排列。此时通过遍历相邻的牛利用max()函数求出安全间隔并累加最终得出该排列下的最小牛棚需求并用它来更新全局最优解min_len。for(int i 1; i n; i){ // 尝试把每一头牛编号1到n放在当前的 step 位置 if(vis[i] 0){ // 如果第 i 头牛还没有被使用过 vis[i] 1; // 标记第 i 头牛已使用 order[step] i; // 记录当前第 step 个位置放的是第 i 头牛 dfs(step 1); // 递归调用去放置下一头牛第 step1 头 vis[i] 0; // 回溯取消第 i 头牛的标记以便在后续循环中尝试其他排列 } } }解析标准的 DFS 生成全排列模板。在当前层step尝试所有尚未使用的牛。进入下一层前打标记vis[i]1从下一层返回后撤销标记vis[i]0即回溯从而保证能够穷举出所有的排列可能。int main(){ ios::sync_with_stdio(false); cin.tie(0); // IO流加速提高输入输出效率 cin n; for(int i 1; i n; i) cin a[i]; for(int i 1; i n; i) cin b[i]; dfs(1); // 从放置第1头牛开始启动深搜 cout min_len; return 0; // 结束程序 }解析主函数负责读取输入数据构建好a[]和b[]数组后直接调用dfs(1)启动搜索。最后输出记录下来的最小长度min_len。主要知识点总结1. 深度优先搜索 (DFS) 与回溯算法本题是经典的全排列生成问题。通过vis[]状态数组和递归调用配合回溯操作撤销标记可以系统、不重不漏地枚举出所有可能的排列组合。2. 贪心思想与极值计算在确定了两头牛的相对顺序后它们之间的安全距离由两者攻击范围的较大值决定max(a[cur], b[last])。这种局部最优的选择构成了全局计算的基石。3. 状态模拟与边界处理将抽象的“排队问题”转化为具体的“数轴长度计算”。特别要注意边界的初始化例如第一头牛不需要左侧的安全距离只需占用 1 个基础长度这在cur_len 1中得到了体现。4. 复杂度分析与算法适用性虽然暴力枚举的时间复杂度达到了阶乘级 O(N!)O(N!) 但结合题目给出的极小数据规模 N≤9N≤9 这种暴力解法不仅不会超时反而是逻辑最清晰、最不易出错的满分策略。这提醒我们在做题时要充分利用数据的约束条件。