欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！
专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。
适合人群：
- 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
- 希望系统学习C++/Python编程的初学者
- 想要提升算法与编程能力的编程爱好者
附上汇总帖：GESP认证C++编程真题解析 | 汇总
【题目来源】
洛谷：[P10377 GESP202403 六级] 好斗的牛 - 洛谷
【题目描述】
你有1 0 9 10^9109个牛棚，从左到右一字排开。你希望把n nn头牛安置到牛棚里。麻烦的是，你的牛很好斗，如果他们附近有其他的牛，他们就会不安分地去挑事。其中，第i ii头牛的攻击范围是( a i , b i ) (a_i, b_i)(ai,bi)，这意味着，如果他的左边a i a_iai个牛棚或者右边b i b_ibi个牛棚有其他牛，它就会去挑事。
你想留下一段连续的牛棚，并把其他牛棚都卖掉。请问您最少需要留下多少牛棚，才能保证至少存在一种方案能够把所有的n nn头牛都安置进剩余的牛棚里，且没有牛会挑事？
【输入】
第一行一个正整数n nn。
第二行n nn个正整数a 1 , a 2 , … a n a_1, a_2, \dots a_na1,a2,…an。
第三行n nn个正整数b 1 , b 2 , … b n b_1, b_2, \dots b_nb1,b2,…bn。
【输出】
输出一行一个整数表示答案。
【输入样例】
2 1 2 1 2【输出样例】
4【算法标签】
《洛谷 P10377 好斗的牛》 #模拟# #搜索# #GESP# #2024#
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;intn;// 牛的数量intflag[15];// 标记数组，用于记录牛是否被使用inta[15];// 排列数组，存储当前排列的牛的顺序intminn=1e9;// 最小总距离，初始化为一个大数structNode{inta;// 牛的左边距离intb;// 牛的右边距离}cow[15];// 牛的信息数组// 深度优先搜索生成全排列voiddfs(intstep){// 如果已经排列完所有牛，计算当前排列的总距离if(step>n){inttot=1;// 初始化总距离，第一头牛需要一个牛棚for(inti=2;i<=n;i++)// 从第二头牛开始计算{// 计算相邻两头牛之间的栅栏距离// 取左边牛的右边距离和右边牛的左边距离的最大值tot+=max(cow[a[i]].a,cow[a[i-1]].b);tot+=1;// 当前这头牛也需要一个牛棚}// 更新最小总距离minn=min(minn,tot);return;}// 生成全排列for(inti=1;i<=n;i++)// 尝试将每头牛放在当前位置{if(!flag[i])// 如果这头牛还没有被使用{flag[i]=1;// 标记为已使用a[step]=i;// 将牛i放在第step个位置dfs(step+1);// 递归放置下一头牛flag[i]=0;// 回溯，取消标记}}}intmain(){// 输入牛的数量cin>>n;// 输入每头牛左边的距离for(inti=1;i<=n;i++){cin>>cow[i].a;}// 输入每头牛右边的距离for(inti=1;i<=n;i++){cin>>cow[i].b;}// 从第一个位置开始深度优先搜索dfs(1);// 输出最小总距离cout<<minn<<endl;return0;}【运行结果】
2 1 2 1 2 4
