Link

Sol

不得不说,虽然JX的同学去年得再考一次联赛,但是同样的报名费,获得了一次翻盘机会,而且这套题的质量也不知道比CSP2019的好到哪里去了

首先64分很好拿,直接Kruskal板子上去就好了

然后你再观察,发现你要是棵生成树,在这样的网格图中会选一段对答案优的横边或者竖边(主要是要强调一段)

用Kruskal的板子把选的边打印出来,你会发现Kruskal选的边一定是权值小的一段一段的出现.

所以就把横边的权值和竖边的权值排序,每次选一排或一列的就可以了.注意这么选是要保证无环的.

Code

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

#define int long long

const int SIZE = 3e5 + 5;

int n, m, num;
int a[SIZE], b[SIZE];

namespace ae86 {
    const int bufl = 1 << 15;
    char buf[bufl], *s = buf, *t = buf;
    inline int fetch() {
        if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
        return *s++;
    }
    inline int read() {
        int a = 0, b = 1, c = fetch();
        while (!isdigit(c))b ^= c == '-', c = fetch();
        while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
        return b ? a : -a;
    }
}
using ae86::read;

inline int cmp(int a, int b) { return a < b; }

signed main() {
    // freopen("code.in", "r", stdin);
    // freopen("code.out", "w", stdout);
    n = read(), m = read();
    for (int i = 1; i <= n; ++ i) a[i] = read();
    for (int i = 1; i <= m; ++ i) b[i] = read();
    std::sort(a + 1, a + n + 1, cmp); std::sort(b + 1, b + m + 1, cmp);
    int ans = (m - 1) * a[1] + (n - 1) * b[1];
    int p = 1, q = 1, cnt1 = 2, cnt2 = 2;
    while (cnt1 <= n && cnt2 <= m) {
        if (a[cnt1] <= b[cnt2]) ans += (a[cnt1 ++] * (m - q)), ++ p;
        else ans += (b[cnt2 ++] * (n - p)), ++ q;
    }
    printf("%lld\n", ans);
    return 0;
}