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

全部评论

相关推荐

06-23 11:43
门头沟学院 Java
allin校招的烤冷...:我靠,今天中午我也是这个hr隔一个星期发消息给我。问的问题还是一模一样的😅
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务