这题就贪心,很容易证明每一个代价都必须分只是分多少次的问题,然后分析发现先分的分的次数更少,所以优先分大的,如果横着分一次,那么竖着就要多分一次,竖着分同理,所以直接排个序再处理一下就好了....
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ll long long
using namespace std;
const int N=1e5;
int n,m;
ll ans;
int x=1,y=1;
struct MS{
int op,x;
}a[N];
int tot;
bool cmp(MS x,MS y){return x.x>y.x;}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n-1;i++)
{
int x;
scanf("%d",&x);
a[++tot].x=x;
a[tot].op=1;
}
for(int i=1;i<=m-1;i++)
{
int x;
scanf("%d",&x);
a[++tot].x=x;
a[tot].op=0;
}
sort(a+1,a+1+tot,cmp);
for(int i=1;i<=tot;i++)
{
if(a[i].op==1)ans+=x*a[i].x,y++;
else ans+=y*a[i].x,x++;
}
printf("%lld",ans);
}
%%%