无线网络发射器选址
程序员文章站
2022-06-12 13:49:47
...
- 首先我们先分析一下这道题,这道题的数据范围不大,因而可以直接用数组,然后选的时候直接进行搜索,查找出最有效的位置(因为就是暴力,这里不给出代码)。
- 但是对于我们这样追求效率的人来说,这样的方法太慢了,这时我们想到,直接在输入时进行对图中的点操作,将它附近可以将它影响的点全部加上他的值,这样我们可以省下许多时间。
- 这样的方法对于这道题来说已经够了,但我们会想,若是处理的数据太多组怎么办呢?我们就可以用前缀和的方式进行操作,具体代码如下:
#include<bits/stdc++.h>/*万能头文件,包含万物,但是联赛时好像不能用。
编译器过不了,平时可以偷一下懒*/
using namespace std;
int g[150][150];
int d,n,x,y,k,ans,num,
xl,xr,yl,yr;
int main()
{
scanf("%d%d",&d,&n);
for(int i=1;i<=n;i++){
scanf("%d%d%d",&x,&y,&k);
xl=max(0,x-d);
xr=x+d;
yl=max(0,y-d);
yr=y+d;
for(int i=xl;i<=xr;i++){
g[i][yl]+=k;
g[i][yr+1]-=k;
}
}
for(int i=0;i<=128;i++)
for(int j=0;j<=128;j++){
g[i][j]+=g[i][j-1];
if(ans<g[i][j]){
ans=g[i][j];
num=1;
}
else if(ans==g[i][j])
num++;
}
printf("%d %d",num,ans);
return 0;
}
如有疑问或问题欢迎在评论中提出
上一篇: SpringCloud微服务概述
下一篇: SpringCloud入门概述