解题思路: 二分+并查集
注意事项:
参考代码:
#include <iostream>
#include <algorithm>
using namespace std;
#define int long long
const int N=2e2;
int n;
struct node{
int x,y;
}a[N];
int fa[N];
int dist[N][N];//记录两坐标间的曼哈顿距离
int find(int x)
{
if(fa[x]==x)
return x;
else
return fa[x]=find(fa[x]);
}
void Union(int x,int y)
{
x=find(x);
y=find(y);
if(x!=y)
fa[x]=y;
}
bool solve(int mid)
{
for(int i=1;i<=n;i++)//初始化并查集
fa[i]=i;
for(int i=1;i<n;i++)
{
for(int j=i+1;j<=n;j++)
{
if(dist[i][j]<=mid*2)//两点间的距离能在mid内连通
Union(i,j);
}
}
int cnt=0;
for(int i=1;i<=n;i++)
{
if(fa[i]==i)
cnt++;
if(cnt==2)//有2个以上就不符合
return false;
}
return true;
}
signed main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i].x>>a[i].y;
for(int i=1;i<n;i++)
{
for(int j=i+1;j<=n;j++)
{
dist[i][j]=dist[j][i]=abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y);
//两点的曼哈顿距离
}
}
int l=0,r=1e9;
while(l<r)//二分答案--时间
{
int mid=(l+r)/2;
if(solve(mid))
r=mid;
else
l=mid+1;
}
cout<<l;
return 0;
}
0.0分
0 人评分
C语言程序设计教程(第三版)课后习题3.7 (C语言代码)浏览:732 |
2006年春浙江省计算机等级考试二级C 编程题(1) (C语言代码)浏览:820 |
C语言程序设计教程(第三版)课后习题11.5 (C语言代码)浏览:1533 |
C语言程序设计教程(第三版)课后习题5.4 (C语言代码)浏览:1311 |
C语言程序设计教程(第三版)课后习题5.4 (C语言代码)浏览:809 |
简单的a+b (C语言代码)浏览:581 |
1051(奇了怪了)浏览:649 |
剪刀石头布 (C++代码)浏览:1712 |
交换Easy (C语言代码)浏览:761 |
第三届阿里中间件性能挑战赛-总决赛亚军比赛攻略浏览:1145 |