自动搬运

查看原文

来自洛谷，原作者为

	xieyuhao2022 The future is promising

搬运于2025-08-24 22:15:53，当前版本为作者最后更新于2022-07-14 14:10:35，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

Solution

我们将题目简化为：现有集合 $X,Y$，里面有已有一些数字。

我们观察题目，不难得出每次切割的代价为，其数值与前面不属于同个集合的数字个数 $+1$ 的乘积。

例如，若横向切下一刀，此时巧克力变为两块，那么竖向切割时就需要切两次，即做两倍代价。以此类推，即可得出上述结论。

进一步分析，我们不难得出应优先选择数值大的进行切割。

对于同个集合，显然数值大的排序靠前更优。

对于不同集合，即不同方向上切割，后切的自然需要在原基础上多切一刀，那么数值大的会越来越大。反之，我们则需要优先选择数值大的。

因此，我们可以将两个集合合并、排序后进行操作。

时间复杂度为 $O(N \log{N})$，可以通过本题。

Code

#include<iostream>
#include<algorithm>
using namespace std;
const int N=2e4+5;	//注意开两倍大小
int n,m,tot,x_,y_;
long long ans;
struct qwq{
	int val,id;
}a[N];
bool cmp(qwq x,qwq y){
	return x.val>y.val;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<n;i++){
		cin>>a[i].val;
		a[i].id=1;
	}
	for(int i=n;i<n+m-1;i++){
		cin>>a[i].val;
		a[i].id=2;
	}
	tot=n-1+m-1;
	sort(a+1,a+1+tot,cmp);
	for(int i=1;i<=tot;i++){	//记录出现过的不同元素
		if(a[i].id==1) ans+=(y_+1)*a[i].val,x_++;
		else ans+=(x_+1)*a[i].val,y_++;
	}
	cout<<ans<<endl;
	return 0;
}