[FZYZOJ 1200] 路由器安置

P1200 -- 路由器安置

时间限制：1000MS

内存限制：131072KB

Description

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

Input Format

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

Output Format

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

Sample Input

Sample Output

1.0

Hint

【样例输出】（在2，10位置上各放一个）

【数据规模】

对于60%的数据，有1 ≤N, M ≤100，-1000 ≤Hi ≤1000；

对于100%的数据，有1 ≤N, M ≤100000，-10000000 ≤Hi ≤10000000。

【题解】

二分答案，然后判断是否符合，枚举即可。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n,m,l,r,mid;
 4 int p[100010];
 5 char B[1<<15],*S=B,*T=B;
 6 char getchar2() {
 7     return S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?0:*S++;
 8 }
 9 int read() {
10     int x=0; int f=1;
11     char ch=getchar2();
12     while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar2();}
13     while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+ch-'0'; ch=getchar2();}
14     return x*f;
15 }
16 int main() {
17     m=read();n=read();
18     for(int i=1;i<=n;i++) p[i]=read();
19     sort(p+1,p+n+1);
20     for(l=0,r=p[n]-p[1],mid=(l+r)/2;l<r;mid=(l+r)/2) {
21         int c=0,to=-987654321;
22         for(int i=1;i<=n;i++)
23             if(p[i]>to) {
24                    c++;
25                    to=p[i]+mid;
26             }
27         if(c>m) l=mid+1;
28         else r=mid;
29     }
30     printf("%.1lf",l/2.0);
31     return 0;
32 }

View Code

0.119s，再一次rank1 =-=