D题有用并查集+set写的吗
D题有用并查集+set写的吗,时间复杂度和二分一样都是O(nlogn),但是一直调试不出来,具体思路是:
初始时将n个区间分开,每次合并相邻区间之间合并代价最小的两个区间,代价最小可以用set或priority_queue维护,但是考虑到合并以后还要删除原有的两个连接,再新添两个连接,所以使用了set,每次合并将两个区间的合并的最小代价加上以后,再使用并查集维护整个区间的左右端点和2,5的数量,但是只通过了10%的样例,求大佬帮忙看一下
int n, k; int p2[N], p5[N], a[N], p[N], l[N], r[N]; ll f[N]; int find(int x) { if (x != p[x])p[x] = find(p[x]); return p[x]; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int _ = 1; //cin >> _; while (_--) { cin >> n >> k; k = n - k; ll ans = 0; for (int i = 1; i <= n; i++) { string s; cin >> s; for (int j = 0; j < s.length(); j++) { if (s[j] == '2') { p2[i]++; } else if (s[j] == '5') { p5[i]++; a[i] += p2[i]; } } p[i] = i; l[i] = i; r[i] = i; //cout << "p2:" << p2[i] << " p5:" << p5[i] << " a:" << a[i] << '\n'; ans += a[i]; } using Node = pair<ll, PII>; set<Node>q; auto get = [&](int l, int r)->ll { return 1ll * p2[l] * p5[r]; }; for (int i = 1; i < n; i++) { f[i] = get(i, i + 1); //cout << i << " " << i + 1 << " " << f[i] << '\n'; q.insert({ f[i], {i,i + 1}}); } /*cout << k << '\n'; for (auto t : q) { cout << t.x << " " << t.y.x << " " << t.y.y << '\n'; }*/ while (k--) { Node t = *q.begin(); q.erase(t); ans += t.x; int u = find(t.y.x); int v = find(t.y.y); int oriu = u, oriv = v; p2[u] += p2[v], p5[u] += p5[v]; l[u] = min(l[u], l[v]); r[u] = max(r[u], r[v]); p[v] = u; if (l[u] > 1) { v = find(l[u] - 1); q.erase({ f[v],{v,u} }); f[v] = get(v, u); q.insert({ f[v],{v,u} }); } if (r[u] < n) { v = find(r[u] + 1); q.erase({ f[oriv],{oriv,v} }); f[u] = get(u, v); q.insert({ f[u],{u,v} }); } /*cout << k << '\n'; for (auto t : q) { cout << t.x << " " << t.y.x << " " << t.y.y << '\n'; }*/ } cout << ans << '\n'; } return 0; }