B 算法萌萌题。
题解
看到完全图求最小生成树,必然是要考虑一下 B 算法能不能做的。
发现这个题的联通块最小值是可以维护的。
我们发现。
假如我们钦定 \(i\) 往前面连。
那么前面的最小权值必然是一个固定的值。
我们一定会连到 \(\min (a_j-j\times D)\) 上。
由于不能连到自己在的联通块上。
所以我们可以维护每一个联通块的最小值。
只需要从前往后扫一遍,用 set 维护即可。
往后面连是同理的。
使用并查集维护联通性即可。
时间复杂度:\(O(n\log n\log n)\)。
Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, D, ans;
int a[200010], f[200010];
int v[200010], s[200010];
int fa[200010];
inline int gf(int x) {
return (fa[x] == x ? x : fa[x] = gf(fa[x]));
}
inline bool chk() {
for (int i = 1; i <= n; i++) {
if (gf(i) != gf(1)) return 1;
}
return 0;
}
signed main() {
cin >> n >> D;
for (int i = 1; i <= n; i++) {
cin >> a[i], fa[i] = i;
}
while (chk()) {
multiset<pair<int, int>> q;
for (int i = 1; i <= n; i++) s[i] = 0, v[i] = 1e18;
for (int i = 1; i <= n; i++) f[i] = 1e18;
q.clear();
for (int i = 1; i <= n; i++) {
int x = gf(i);
if (f[x] < 1e18) q.erase(q.find({f[x], x}));
if (q.empty() == 0) {
if (v[x] > q.begin()->first + a[i] + i * D) {
v[x] = q.begin()->first + a[i] + i * D;
s[x] = q.begin()->second;
}
}
if (f[x] > a[i] - i * D) {
f[x] = a[i] - i * D;
}
q.insert({f[x], x});
}
for (int i = 1; i <= n; i++) f[i] = 1e18;
q.clear();
for (int i = n; i >= 1; i--) {
int x = gf(i);
if (f[x] < 1e18) q.erase(q.find({f[x], x}));
if (q.empty() == 0) {
if (v[x] > q.begin()->first + a[i] - i * D) {
v[x] = q.begin()->first + a[i] - i * D;
s[x] = q.begin()->second;
}
}
if (f[x] > a[i] + i * D) {
f[x] = a[i] + i * D;
}
q.insert({f[x], x});
}
vector<int> r;
for (int i = 1; i <= n; i++)
if (s[i]) {
int x = gf(i), y = gf(s[i]);
if (x != y) fa[x] = y, ans += v[i];
}
}
cout << ans << "\n";
}
标签:begin,int,题解,200010,fa,Connecting,Cities,first
From: https://www.cnblogs.com/JiaY19/p/18400234