首页 > 试题广场 >

牛之国

[编程题]牛之国
  • 热度指数：280 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
牛之国有个城市，牛牛作为牛之国国王，他希望所有牛之国的城市能够连通起来。现在他下令牛之国的所有施工队同时施工，同时已知牛之国的施工队的施工速度均为1距离单位/年，对于每个城市，城市的领导者都会向每个相邻的城市派出施工队进行修路（所有城市相邻），并且每个施工队都按照最短的路线修路，如果两个施工队碰头，那么两个城市相连。
现在给你个城市的坐标，牛牛想知道牛之国的城市最少需要多少年才能全部连通(城市A和城市B连通，当且仅当A到B有一条通路)。

输入描述:
第一行一个整数 (1 \leq n \leq 1000)，表示城市数量。
接下来行每行两个整数x_{i} (-10^8 \leq x_{i} \leq 10^8) ,y_{i} (-10^8 \leq y_{i} \leq 10^8)用空格分隔，表示城市的坐标。


输出描述:
输出仅有一个整数，表示城市相连需要的年数向上取整的结果。
例如，如果需要2.5年可以连通，请输出 3，如果如要 4 年可以连通，请输出 4。
示例1

输入

3
0 0
0 5
6 0

输出

3

说明

当(6,0)和(0,0)连在一起时，所有城市连在一起，此时需要3年。
示例2

输入

2
0 0
1 0

输出

1

说明

初始不连通，0.5年可以连通，向上取整得到 1。

备注:
python选手请使用pypy提交
算法知识视频讲解
查看答案及解析
添加回答
这个ID应该没人用头像 这个ID应该没人用
二分法枚举最少年数，用dfs判断该年数内修好的路能否将全部城市连通起来，不断缩小搜索范围来找到目标值，时间复杂度N*logN
发表于 2025-09-09 13:18:46 回复(0)
骆亮头像 骆亮
核心：最小生成树（kruskal），需要了解一下，因为我后面只讲了关键点，不然看不懂
关键：记录每个连通块的城市数量,count[i]表示i号城市为根节点的连通块的城市数量
全联通判断：father_node[i]!=father_node[j] & count[i]+count[j]=n
答案：循环添加边时，第一个满足全联通判断的i，j两点的距离除以2再向上取整

发表于 2025-07-26 00:53:54 回复(0)
提交观点

问题信息

计算几何 京东 图
难度：
2条回答 452浏览

热门推荐

相关试题

牛之国

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号