题解 | #信号覆盖#

信号覆盖

https://www.nowcoder.com/practice/35175cee9e634b92b35b634244d81feb

#include<bits/stdc++.h> 

using namespace std;

vector<int> xarr,yarr;

struct Node{
    int u,v; // 点!
    int dis;
    Node(int _u,int _v,int _dis):u(_u),v(_v),dis(_dis){}
    
    bool operator <(const Node& node){
        return dis < node.dis;
    }
    
} ;


int find(vector<int>& father,int u){
    if(father[u] == u) return u;
    return find(father,father[u]);
}


int distance(int u,int v){
    int xx = xarr[u] - xarr[v];
    int yy = yarr[u] - yarr[v];
    return xx*xx + yy*yy;
}

int main(){
    int n,k;
    cin >> n >> k;
    xarr.resize(n); yarr.resize(n);
    
    
    for(int i = 0; i < n; i++){
        cin >> xarr[i] >> yarr[i];
    }
    
    vector<Node> arr;
    
    for(int i = 0; i < n; i++){
        for(int j = i+1; j < n; j++){
            arr.emplace_back(Node(i,j,distance(i,j)));
        }
    }
    
    sort(arr.begin(),arr.end());
    
    if(k == 1){
        cout << 0 << endl;
        return 0;
    }
    
    vector<int> father(n);
    
    for(int i = 0; i < n; i++) father[i] = i;
    
    vector<int> size(n,1);
    
    for(Node node : arr){
        int f1 = find(father,node.u);
        int f2 = find(father,node.v);
        
        if(f1 != f2){
            father[f1] = f2;
            size[f2] += size[f1];
            if(size[f2] >= k){
                cout << node.dis << endl;
                return 0;
            }
        }
       
    }
    assert(0);
    return 0;
}

全部评论

相关推荐

门口唉提是地铁杀:之前b站被一个游戏demo深深的吸引了。看up主页发现是个初创公司,而且还在招人,也是一天60。二面的时候要我做一个登录验证和传输文件两个微服务,做完要我推到github仓库,还要我加上jaeger和一堆运维工具做性能测试并且面试的时候投屏演示。我傻乎乎的做完以后人家跟我说一句现在暂时不招人,1分钱没拿到全是白干
你的秋招第一场笔试是哪家
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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