[HAOI2009] 巧克力

有一个 (n imes m) 的矩形巧克力，沿着第 (i) 条横线切一次代价为 (a_i)，沿着第 (i) 条竖线切一次代价为 (b_i)，求切割完的最小代价。

Solution

显然对于相同方向的，我们会先切大的再切小的

对于不同类型的，设已经横切 (x) 次，纵切 (y) 次，那么先切横的代价就是 ((s_1+1)a+(s_2+2)b)，反之则为 ((s_1+2)a+(s_2+1)b)，若前者大于后者，等价于 (b>a)，于是我们发现切割顺序与方向无关，只需要先切大的就可以了

#include <bits/stdc++.h>
using namespace std;

const int N = 20005;

struct item {
    int p,q;
    bool operator < (const item &b) {
        return p > b.p;
    }
} s[N];

int n,m,a[N],b[N];

signed main() {
    cin>>n>>m;
    for(int i=1;i<n;i++) cin>>a[i], s[i]={a[i],1};
    for(int i=1;i<m;i++) cin>>b[i], s[i+n-1]={b[i],2};
    int s1=0,s2=0,ans=0;
    sort(s+1,s+n+m-1);
    for(int i=1;i<=n+m-2;i++) {
        if(s[i].q==1) {
            ans+=s[i].p*(s2+1);
            ++s1;
        }
        else {
            ans+=s[i].p*(s1+1);
            ++s2;
        }
    }
    cout<<ans;
}