[CF 457B] Distributed Join

作法：

感覺題目寫的不太好懂......簡單來說就是，現在有左邊$n$坨資料，右邊$m$坨資料，每坨資料裡都有一定數量的行。一次操作可以把某一行複製到某坨資料中塞進去，問至少要幾次操作才能滿足在左邊任選一行，右邊任選一行，都有某一坨資料裡面含了這兩行（任兩行的內容都不一樣）。首先觀察最佳解會有怎樣的特性，對於某一行來說，簡稱「這一行被複製到了哪幾坨資料」為他的目的地，那麼某坨資料中的所有行的目的地都一樣。因為如果某坨中有兩行的目的地不一樣（假設這坨在左邊），對於其中一種目的地來說，那幾坨的聯集裡面一定包含了所有右邊的行，因此可以把目的地坨數比較多的那個方法換成比較少的，這樣答案不會更差，因此一坨資料中任兩行的目的地相同。再來則是最佳解中至少有一坨資料內的每一行是沒被複製過的（之後簡稱這件事為這坨資料不動），因為如果每坨的資料都有動，那麼隨便取一坨，稱他為$A$，考慮這坨資料的目的地集合$S$和所有進行過的操作，把所有「把某行複製到$S$中某一坨」的操作都替換成「把那行複製到$A$」，顯然這樣替換還是可以滿足原題條件，並且總複製次數不會增加。因為這裡的假設是每坨資料都有動，因此不會發生「某坨資料的目的地集合嚴格變大」這件事（否則代表他原本的目的地集合就是空集合）。

因此我們可以假設右邊有一坨資料不動，之後將左右的資料對調再求一次答案即可。不妨設右邊不動的資料們的行數分別為$b_1,...,b_k$，剩下的為$b_{k+1},...,b_m$，那麼因為這幾坨都不動，所以對於左邊的每一行都要複製進$b_1,...,b_k$的每坨資料中，這需要花$k\cdot (a_1+...+a_n)$次操作。而因為$b_{k+1},...,b_m$都有動，也就是他們的目的地至少有一個，所以這部份至少要進行$b_{k+1}+...+b_m$次操作。而我們的確可以只用$k\cdot (a_1+...+a_n)+b_{k+1}+...+b_m$完成任務，只要把$b_{k+1},...,b_m$中每一行都複製進$b_1$就可以了。因此對於固定的$k$來說，取$b$中前$k$大的數是最好的，所以只要先把$b$由大到小排序，掃過去並維護前綴和就可以了。

code :

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=100000+10 ;
 
int n,m ;
int a[maxn],b[maxn] ;
LL solve()
{
    LL sa=0,sb=0,ret=1LL<<60 ;
    for(int i=1;i<=n;i++) sa+=a[i] ;
    for(int i=m;i>=1;i--)
    {
        if(ret>sb && (ret-sb)/i>sa-2)
            ret=min(ret,i*sa+sb) ;
        sb+=b[i] ;
    }
    return ret ;
}
main()
{
    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+1,greater<int>()) ;
    sort(b+1,b+m+1,greater<int>()) ;
    LL ans=solve() ;
    swap(a,b) ; swap(n,m) ;
    printf("%I64d\n",min(ans,solve())) ;
}