自动搬运

查看原文

来自洛谷，原作者为

	dingcx 不如回头再看一眼题面

搬运于2025-08-24 21:23:46，当前版本为作者最后更新于2020-01-03 21:59:43，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

由于没有一次AC这道题，所以来发一篇题解。

思路

话说这道题标签已经把思路全部表示出来了。。。

问题在于怎么贪心。

样例实在是太水了，以至于怎么切得到的答案都是$9$。

推荐一组样例：

输入
4 2
4 5 6
1
输出
19

解释一下这组样例。图长这样：

如果先切横的，结果就是$1+2*4+2*5+2*6=31$。

如果先切竖的，结果就是$4+5+6+1*4=19$。

显然先切竖的更优。

由此，可以得出一个结论：先切代价大的。

于是，思路就出来了。先把两个数组从大到小排序，然后两个数组挨个比较，较大的就在答案上加上这个代价（要乘上切了多少刀），再把指针往后挪一位，直到全部算完即可。

细节

这道题细节还是蛮多的。（也就是我没有一次AC的原因）

1.是先取大的，不是先取小的。

2.注意是$n-1$和$m-1$，不能算成$n$和$m$。

3.最后的答案要开long long。

于是就可以愉快地AC了！

代码

相信所有人都会看这里吧（有没有干不好的事情我就不知道了），不过为了题解的完整性，我还是把代码附上——

（应该是史上最短）

#include<cstdio>
#include<algorithm>//用到sort
using namespace std;
const int MAXN=2020;//毕竟刚刚2020~
int a[MAXN],b[MAXN];//横线和竖线的代价
bool cmp(int aa,int bb){return aa>bb;}//从大到小
int main(){
	int n,m,s1=1,s2=1;//s1和s2可以是a数组和b数组的指针，也可以是横纵分成的块数
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++) scanf("%d",&a[i]);
	for(int i=1;i<m;i++) scanf("%d",&b[i]);
	sort(a+1,a+n,cmp);sort(b+1,b+m,cmp);//从大到小排序
	long long ans=0;//记录答案，注意long long
	for(int i=2;i<n+m;i++){//遍历
		if(a[s1]>b[s2]) ans+=s2*a[s1++];//选择大的，这里s2表示块数，s1指针后移一位
		else ans+=s1*b[s2++];//同理，和上面相反
	}
	printf("%lld",ans);
	return 0;//华丽结束
}

看我这么辛苦写一篇题解，总得点个赞再走呀~