自动搬运

查看原文

来自洛谷，原作者为

	Ice_rnfmabj 请保持缄默，我们一直都在

搬运于2025-08-24 22:58:25，当前版本为作者最后更新于2024-05-19 20:10:11，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

猫猫不可以劈开！猫猫不可以劈开！！猫猫不可以劈开！！！

如果你看了讨论区，你会发现有一种做法，先加上所有猫的体重然后除以缆车的载重。但是很明显这样有时候猫就会被切开。

所以我想正解是 DFS，因为要求的是最少用几辆缆车，那么就先从大到小排个序，然后一只一只猫放到缆车里。当然，要最大化缆车的利用，那么就需要尽可能把猫塞进缆车里。

下面的代码里，我用 $a_i$ 表示每只猫的体重，$sum_i$ 代表第 $i$ 号缆车现在的重量。如果 $sum_i$ 加上 $a_u$ 还小于等于载重的话，那就加上 $a_u$，然后进行下一层 DFS。当然 DFS 完之后还要还原回去。

但是以上是还能塞猫的情况，有时候猫太重了就只能再来一辆缆车了。所以出了循环，把 $a_u$ 放进 $sum_v$ 里，然后 DFS 下一层，开一个新的缆车并且用后面的猫。

#include<bits/stdc++.h>
using namespace std;
int n,m,a[101],ans,sum[101];
void dfs(int u,int v){
	if(v>=ans) return;
	if(u==n){
		ans=v;
		return;
	}
	for(int i=0;i<v;i++){
		if(sum[i]+a[u]<=m){
			sum[i]+=a[u];
			dfs(u+1,v);
			sum[i]-=a[u];
		}
	}
	sum[v]=a[u];
	dfs(u+1,v+1);
	sum[v]=0;
}
int main(){
	cin>>n>>m;
	ans=n;
	for(int i=0;i<n;i++) cin>>a[i];
	sort(a,a+n,greater<int>());
	dfs(0,0);
	cout<<ans;
	return 0;
}