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;
}