CF457B. Distributed Join

题目链接
大意：有两个数组a，b，你可以把任何一个数组的任何一个位置的元素复制到任何一个数组的任何一个位置，你需要使得两个数组中的任意两个位置（分别来自两个数组）都存在于一个相同的位置，复制的代价是元素值，问最小代价？
思路：显然我们有两种策略：
1.把一些位置都复制到一个位置上，那么这些位置就都满足
2.对于一个数组的一个位置来说，每次选择把自己复制到另一个数组的某个位置，或者把另一个数组的某个位置复制到当前位置上（根据大小来定）。
先对两个数组按元素值从小到大排序。
那么我们枚举这两种操作的分界点来统计最小答案即可。
细节见代码：

#include<bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define LL long long
#define SZ(X) X.size()
#define pii pair<int,int>
#define ALL(X) X.begin(),X.end()

using namespace std;

LL gcd(LL a, LL b) {return b ? gcd(b, a % b) : a;}
LL lcm(LL a, LL b) {return a / gcd(a, b) * b;}
LL powmod(LL a, LL b, LL MOD) {LL ans = 1; while (b) {if (b % 2)ans = ans * a % MOD; a = a * a % MOD; b /= 2;} return ans;}
const int N = 1e5 + 11;
int n,m;
LL a[N],b[N];
LL A[N],B[N];
int main() {
	ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=m;i++)cin>>b[i];
    sort(a+1,a+1+n);
    sort(b+1,b+1+m);
    for(int i=1;i<=n;i++)A[i]=A[i-1]+a[i];
    for(int i=1;i<=m;i++)B[i]=B[i-1]+b[i];
    LL ans=LLONG_MAX,pre=0;
    for(int i=n;i>=1;i--){
        int pos=upper_bound(b+1,b+1+m,a[i])-b;
        LL res=B[pos-1];
        res+=1ll*(m-pos+1)*a[i];
        pre+=res;
        if(ans<=pre+(i>1?(B[m]+A[i-1]-max(a[i-1],1ll*b[m])):0))break;
        ans=pre+(i>1?(B[m]+A[i-1]-max(a[i-1],1ll*b[m])):0);
    }
    pre=0;
    for(int i=m;i>=1;i--){
        int pos=upper_bound(a+1,a+1+n,b[i])-a;
        LL res=A[pos-1];
        res+=1ll*(n-pos+1)*b[i];
        pre+=res;
        if(ans<=pre+(i>1?(A[n]+B[i-1]-max(b[i-1],1ll*a[n])):0))break;
        ans=pre+(i>1?(A[n]+B[i-1]-max(b[i-1],1ll*a[n])):0);
    }
    cout<<min({ans,A[n]+B[m-1],A[n-1]+B[m]})<<endl;
	return 0;
}