路由器放置 8716

常规
1

路由器放置
可以讲一下check的思路吗？

1 个赞
2

2. 路由器放置

题目ID：8716必做题100分

最新提交：0 分

历史最高：0 分

时间限制: 1000ms

空间限制: 262144kB

题目描述

题目描述

一条街道安装WIFI，需要放置M个TP-LINK路由器。整条街道上一共有N户居民，分布在一条直线上，每一户居民必须被至少一台TP-LINK路由器覆盖到。现在的问题是所有TP-LINK路由器的覆盖半径是一样的，我们希望用覆盖半径尽可能小的路由器来完成任务，因为这样可以节省成本。

输入格式

输入文件第一行包含两个整数M和N，以下N行每行一个整数H(i)表示该户居民在街道上相对于某个点的坐标。

输出格式

输出文件仅包含一个数，表示最小的覆盖半径，保留一位小数。

样例数据

input

2 3
1
3
10

output

1.0

数据规模与约定

时间限制：1s

空间限制：256MB

注释

对于 60%60% 的数据，有 1≤ �,�≤ 100，−1000≤ ��≤ 10001≤ N,M≤ 100，−1000≤ Hi​≤ 1000； 对于 100%100% 的数据，有 1≤ �,�≤ 100000，−10000000≤ ��≤ 100000001≤ N,M≤ 100000，−10000000≤ Hi​≤ 10000000。

1 个赞
3 
2. 路由器放置

题目ID：8716
必做题

最新提交：

> 时间限制: 1000ms
>
>
>
> 空间限制: 262144kB

题目描述

 题目描述

一条街道安装WIFI，需要放置M个TP-LINK路由器。整条街道上一共有N户居民，分布在一条直线上，每一户居民必须被至少一台TP-LINK路由器覆盖到。现在的问题是所有TP-LINK路由器的覆盖半径是一样的，我们希望用覆盖半径尽可能小的路由器来完成任务，因为这样可以节省成本。

#### 输入格式

输入文件第一行包含两个整数M和N，以下N行每行一个整数H(i)表示该户居民在街道上相对于某个点的坐标。

#### 输出格式

输出文件仅包含一个数，表示最小的覆盖半径，保留一位小数。

2 3
1
3
10

1.0



时间限制：1s

空间限制：256MB
3 个赞
4 
#include<bits/stdc++.h>
using namespace std;
double inf=1E-2;
int n,m;
double L=0.0,R=20000000.0,mid;
double ans=0.0;
int TP_LINK[100005];
bool check(int x)
{
	int sum=TP_LINK[1]+2*x;
	int ans=1;
	for(int i=2;i<=n;i++)
	{
		if(TP_LINK[i]>sum)
		{
			sum=TP_LINK[i]+2*x;
			ans++; 
		}
	}
	if(ans>m)
	{
		return false;
	}
	return true;
}
int main()
{
	cin>>m>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>TP_LINK[i];
	}
	sort(TP_LINK+1,TP_LINK+n+1);
	L=L-1;
	R=R+1;
	while(L+inf<R)
	{
		mid=(L+R)/2.0;
		if(check(mid)==true)
		{
			R=mid;
		}
		else
		{
			L=mid;
		}
	}
	printf("%.1lf",R);
	return 0;
}
2 个赞