自动搬运

查看原文

来自洛谷，原作者为

	wasa855 您强归您强，您没有 xyr2005 强

搬运于2025-08-24 21:41:24，当前版本为作者最后更新于2018-10-16 16:46:41，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

首先此题一定要先对两个数组排序。
然后采用动态规划的思想，定义f[i][j]=前i只猴子上前j棵树的消耗的最小能量。
对于转移方程：如果j==1，即只有一棵树，那么f[i][j]必然等于f[i-1][j]+abs(a[i]-b[j])。
如果j==i，即i只猴子上i棵树，又因为每棵树上必有一致猴子，f[i][i]必然等于f[i-1][i-1]+abs(a[i]-b[i])。
对于其他情况，有两种情况，第一是第i只猴子独占第j棵树，第二是第i只猴子和其他猴子共享第j棵树，即从min(f[i-1][j],f[i-1][j-1])转移而来，最后加上abs(a[i]-b[j])就好了。
看到数据范围，最后结果可能会超过$int(c++)$的范围，所以要开$long long(c++)$，但经计算需要约$190MB$的空间，所以要开滚动数组。

最后，祝大家$NOIP2018 RP++$。

附上代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 4611686018427387903
ll mon[5005];
ll tree[5005];
ll f[2][5005];
int main()
{
	int n,m;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&mon[i]);
	}
	cin>>m;
	for(int i=1;i<=m;i++)
	{
		scanf("%lld",&tree[i]);
	}
	sort(mon+1,mon+n+1);
	sort(tree+1,tree+m+1);
	f[1][1]=abs(mon[1]-tree[1]);
	for(int i=2;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(j==1)
			{
				f[i%2][1]=f[(i-1)%2][1]+abs(mon[i]-tree[j]);
				continue;
			}
			if(i==j)
			{
				f[i%2][j]=f[(i-1)%2][j-1]+abs(mon[i]-tree[j]);
				break;
			}
			f[i%2][j]=min(f[(i-1)%2][j],f[(i-1)%2][j-1])+abs(mon[i]-tree[j]);
		}
	}
	cout<<f[n%2][m]<<endl;
	return 0;
}