小L的空投

链接

这道题很容易想到要用并查集,我们只需要用逆向思维

但是,由于数据很大,对于cnt(需要的空投数)不能每次都计数,而是需要实时更新

我们不妨思考,当两个城市合并时,如果二者的根节点不同,那么我们就检查这两个城市的连通块数量,如果大于等于d,cnt就减一,合并完再加上即可

#include<bits/stdc++.h>
using namespace std;
#define ll long long
vector<ll>tree;
int n,m,x,d;
int cnt=0;
struct node{
    ll h;
    int idx;
    bool operator<(const node& other) const{
        return h>other.h;
    }
};
int Find(int x);
void Union(int x,int y);


void solve(){
    cin>>n>>m>>x>>d;
    tree.resize(n,-1);
    vector<node>road(n);
    for(int i=0;i<n;i++){
        cin>>road[i].h;
        road[i].idx=i;
    }
    sort(road.begin(),road.end());
    unordered_map<int,vector<int>>mp;
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        mp[a-1].push_back(b-1);
        mp[b-1].push_back(a-1);
    }
    vector<ll>H(x);
    for(int i=0;i<x;i++){
        cin>>H[i];
    }
    vector<int>ans(x);
    int index=0;
    vector<bool>des(n,0);
    for(int i=x-1;i>=0;i--){
        int it=upper_bound(road.begin(),road.end(),H[i],[](ll val,node x){
            return val>=x.h;
        })-road.begin();
        for(int j=index;j<it;j++){
            des[road[j].idx]=1;
            if(d==1) cnt++;
        }
        for(int j=index;j<it;j++){
            int idx=road[j].idx;
            for(int other:mp[idx]){
                if(des[other]){ 
                    Union(idx,other);
                }
            }
        }
        index=it;
        ans[i]=cnt;
//         for(int i=0;i<n;i++){
//             cout<<tree[i]<<" ";
//         }
//         cout<<'\n';
    }
    for(int num:ans) cout<<num<<'\n';
}


int Find(int x){
    if(tree[x]<0) return x;
    else return tree[x]=Find(tree[x]);
}
void Union(int x,int y){
    int root_x=Find(x);
    int root_y=Find(y);
    if(root_x==root_y) return;
    if(-tree[root_x]>=d) cnt--;
    if(-tree[root_y]>=d) cnt--;
    
        if(root_x<root_y){
            tree[root_x]+=tree[root_y];
            tree[root_y]=root_x;
            if(-tree[root_x]>=d) cnt++;
        }
        else{
            tree[root_y]+=tree[root_x];
            tree[root_x]=root_y;
            if(-tree[root_y]>=d) cnt++;
        }
    
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
}

题目限制3s,而这个代码能控制在900ms,很好!