WiFi

WiFi

时间： 1ms        内存：128M

描述：

One day, the residents of Main Street got together and decided that they would install wireless internet on their street, with coverage for every house. Now they need your help to decide where they should place the wireless access points. They would like to have as strong a signal as possible in every house, but they have only a limited budget for purchasing access points. They would like to place the available access points so that the maximum distance between any house and the access point closest to it is as small as possible.

Main Street is a perfectly straight road. The street number of each house is the number of metres from the end of the street to the house. For example, the house at address 123 Main Street is exactly 123 metres from the end of the street.

 

输入：

The first line of input contains an integer specifying the number of test cases to follow. The first line of each test case contains two positive integers n, the number of access points that the residents can buy, and m, the number of houses on Main Street. The following m lines contain the house numbers of the houses on Main Street, one house number on each line. There will be no more than 100 000 houses on Main Street, and the house numbers will be no larger than one million.

输出：

For each test case, output a line containing one number, the maximum distance between any house and the access point nearest to it. Round the number to the nearest tenth of a metre, and output it with exactly one digit after the decimal point.

示例输入：

1
2 3
1
3
10

示例输出：

1.0

提示：

参考答案（内存最优[1232]）：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

#define MP make_pair
#define A first
#define B second

#define PB push_back
#define FR(i, a, b) for(int i=(a); i<(b); i++)
#define FOR(i, n) FR(i, 0, n)
#define RF(i, a, b) for(int i=(b)-1; i>=(a); i--)
#define ROF(i, n) RF(i, 0, n)
#define EACH(it,X) for(__typeof((X).begin()) it=(X).begin(); it!=(X).end(); ++it)

#define MAXN 110000

int lis[MAXN],n,m,ans,del;

int work(int len){
  int pre,cou;
  if(len<0) return 0;
  pre=-(1<<20);
  cou=0;
  FOR(i,n)
    if(lis[i]>pre+len){
      pre=lis[i];
      if(++cou>m) return 0;
    }
  return 1;
}

int main(){
  int ct;
  scanf("%d",&ct);
  while(ct--){
    scanf("%d%d",&m,&n);
    FOR(i,n) scanf("%d",&lis[i]);
    sort(lis,lis+n);
    ans=del=1<<20;
    while(del){
      if(work(ans-del)) ans-=del;
      del/=2;
    }
    printf("%d.%d\n",ans/2,(ans%2==0)?0:5);
  }
  return 0;
}

参考答案（时间最优[4]）：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

#define MP make_pair
#define A first
#define B second

#define PB push_back
#define FR(i, a, b) for(int i=(a); i<(b); i++)
#define FOR(i, n) FR(i, 0, n)
#define RF(i, a, b) for(int i=(b)-1; i>=(a); i--)
#define ROF(i, n) RF(i, 0, n)
#define EACH(it,X) for(__typeof((X).begin()) it=(X).begin(); it!=(X).end(); ++it)

#define MAXN 110000

int lis[MAXN],n,m,ans,del;

int work(int len){
  int pre,cou;
  if(len<0) return 0;
  pre=-(1<<20);
  cou=0;
  FOR(i,n)
    if(lis[i]>pre+len){
      pre=lis[i];
      if(++cou>m) return 0;
    }
  return 1;
}

int main(){
  int ct;
  scanf("%d",&ct);
  while(ct--){
    scanf("%d%d",&m,&n);
    FOR(i,n) scanf("%d",&lis[i]);
    sort(lis,lis+n);
    ans=del=1<<20;
    while(del){
      if(work(ans-del)) ans-=del;
      del/=2;
    }
    printf("%d.%d\n",ans/2,(ans%2==0)?0:5);
  }
  return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。