自动搬运

查看原文

来自洛谷，原作者为

	xyx404 发接龙拉黑 | 新初三|蒟蒻| Link3 聚合页 link3.cc/xyx404 | 个人博客链接 xyx404.github.io

搬运于2025-08-24 22:57:23，当前版本为作者最后更新于2024-04-26 18:44:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路：

考虑到 $n$ 的最大值只有九，所以可以使用 dfs 算法枚举组合方案，把每一头牛的放置顺序存入一个数组中，当把所有的牛都放好后，算出需要的牛棚，最后输出最小值就可以了。

如何算出需要的牛棚，先画张图。

观察这张图，可以分四种情况。

第一种情况，上一头牛的 $b$ 大于现在这头牛的 $a$，那么距离是上一头牛的 $b$，如下图。

第二种情况，上一头牛的 $b$ 等于现在这头牛的 $a$，那么这两个数都可以是距离，如下图。

第三种情况，上一头牛的 $b$ 小于现在这头牛的 $a$，那么距离是这头牛的 $a$，如下图。

第四种情况，没有上一头牛，也就是第一头牛，没有距离，循环直接从第二个放入牛的开始，如下图。

通过上述分析可以看出，距离是上一头牛的 $b$ 与这头牛的 $a$ 中的最大值。

需要注意的是求完距离后要考虑这一头牛也需要一个牛棚，所以每次求出距离后还要加一才可以算出需要的牛棚，要提前处理第一头牛，可以直接将求需要的牛棚的变量赋值为一。

完整代码带注释：

代码与思路完全相同。

#include<bits/stdc++.h>
using namespace std;
struct node{
	int a,b;
}cows[10];// 定义结构体 cows 其实可以不用结构体因为刚开始想的是排序所以用的是结构体但后面不知道怎么排也不想改就这样了
int n,minn=INT_MAX;// 定义把 minn 赋值为 int 的最大值 
bool bj[10];// 标记数组 
int fzsx[10];// 存放置顺序的数组 
void add(){
	int sum=1;// 定义 sum 赋值为 1 因为第一头牛也需要一个牛棚 
	for(int i=2;i<=n;i++){// 从 2 开始因为我们求的是这头牛和上一头牛的距离 
		sum+=max(cows[fzsx[i]].b,cows[fzsx[i-1]].a);// 求这头牛和上一头牛的距离
		sum+=1;// 为什么要加 1 因为上面只是求出了距离这头牛也要一个牛棚 
	}
	minn=min(minn,sum);// 取最小值 
    return ;
}
void dfs(int x){// 通过 dfs 求出组合方案 
	if(x-1==n){// 为什么要 x-1==n 因为我们是从第一个开始搜的当搜完最后一个时再次调用 dfs 时 x 会比 n 大 1 
		add();// 调用 add 函数 
		return ;// 返回空因为 dfs 是 void 类型的 
	}
	for(int i=1;i<=n;i++){
		if(!bj[i]){
			bj[i]=1;// 标记 
			fzsx[x]=i;// 记录 
			dfs(x+1);// 求下一个数 
			bj[i]=0;// 还原 
		}
	}
} 
int main(){
	cin>>n;// 输入 n 
	for(int i=1;i<=n;i++){// 输入 a 
		cin>>cows[i].a;
	}
	for(int i=1;i<=n;i++){// 输入 b 
		cin>>cows[i].b;
	}
	dfs(1);//从第一个开始找 
	cout<<minn<<"\n";// 输出最小值 
	return 0;
}