华师一附中OI组

标题: P2038 无线网络发射器选址 [打印本页]
作者: 李思矿    时间: 2018-6-5 17:12
标题: P2038 无线网络发射器选址
题目描述
随着智能手机的日益普及，人们对无线网的需求日益增大。某城市决定对城市内的公共场所覆盖无线网。
假设该城市的布局为由严格平行的 129129 条东西向街道和 129 条南北向街道所形成的网格状，并且相邻的平行街道之间的距离都是恒定值 1 。东西向街道从北到南依次编号为 0,1,2…128 ，南北向街道从西到东依次编号为 0,1,2 ... 128 。
东西向街道和南北向街道相交形成路口，规定编号为 x 的南北向街道和编号为 yy 的东西向街道形成的路口的坐标是 (x, y) 。在某些路口存在一定数量的公共场所。
由于政府财政问题，只能安装一个大型无线网络发射器。该无线网络发射器的传播范围是一个以该点为中心，边长为 2d 的正方形。传播范围包括正方形边界。
现在政府有关部门准备安装一个传播参数为 d 的无线网络发射器，希望你帮助他们在城市内找出合适的路口作为安装地点，使得覆盖的公共场所最多。

输入输出格式
输入格式：
第一行包含一个整数 d ，表示无线网络发射器的传播距离。
第二行包含一个整数 n ，表示有公共场所的路口数目。
接下来 n行，每行给出三个整数 x, y, k，中间用一个空格隔开，分别代表路口的坐标 (x, y) 以及该路口公共场所的数量。同一坐标只会给出一次。

输出格式：
输出一行，包含两个整数，用一个空格隔开，分别表示能覆盖最多公共场所的安装地点方案数，以及能覆盖的最多公共场所的数量。

输入输出样例
输入样例#1：
  1. 1
  2. 2
  3. 4 4 10
  4. 6 6 20
复制代码

输出样例#1：
  1. 1 30
复制代码


说明
对于100%的数据， 10000001≤d≤20,1≤n≤20,0≤x≤128,0≤y≤128,0<k≤1000000


作者: 李思矿    时间: 2018-6-5 17:12
暴力枚举每个交点就好了
  1. #include<iostream>
  2. using namespace std;
  3. int d,n,G[130][130],x,y,k,ans1,ans2;
  4. int main()
  5. {
  6.     cin>>d>>n;
  7.     while(n--)
  8.     {
  9.         cin>>x>>y>>k;
  10.         G[x][y]=k;
  11.     }
  12.     for(int i=0;i<=128;i++)
  13.         for(int j=0;j<=128;j++)
  14.         {
  15.             int hjj=0;
  16.             for(int a=max(0,i-d);a<=min(128,i+d);a++)
  17.                 for(int b=max(0,j-d);b<=min(128,j+d);b++)
  18.                     hjj+=G[a][b];
  19.             if(hjj==ans2)
  20.                 ans1++;
  21.             else if(hjj>ans2)
  22.             {
  23.                 ans1=1;
  24.                 ans2=hjj;
  25.             }
  26.         }
  27.     cout<<ans1<<' '<<ans2;
  28.     return 0;
  29. }
复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2