欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

无线网络发射器选址

程序员文章站 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;
}

如有疑问或问题欢迎在评论中提出

相关标签: NOIP