題目描述

隨著智能手機的日益普及，人們對無線網的需求日益增大。某城市決定對城市內的公共場所覆蓋無線網。

假設該城市的布局為由嚴格平行的 \(129\) 條東西向街道和 \(129\) 條南北向街道所形成的網格狀，并且相鄰的平行街道之間的距離都是恒定值$ 1$。東西向街道從北到南依次編號為 \(0,1,2...128\)和\(0,1,2…128\)，南北向街道從西到東依次編號為$ 0,1,2…128$。

東西向街道和南北向街道相交形成路口，規定編號為 \(x\) 的南北向街道和編號為 \(y\) 的東西向街道形成的路口的坐標是$ (x, y)$。在某些路口存在一定數量的公共場所。

由于政府財政問題，只能安裝一個大型無線網絡發射器。該無線網絡發射器的傳播范圍是一個以該點為中心，邊長為 $2d $的正方形。傳播范圍包括正方形邊界。

現在政府有關部門準備安裝一個傳播參數為 $d $的無線網絡發射器，希望你幫助他們在城市內找出合適的路口作為安裝地點，使得覆蓋的公共場所最多。

輸入格式

第一行包含一個整數$ d$，表示無線網絡發射器的傳播距離。

第二行包含一個整數 \(n\)，表示有公共場所的路口數目。

接下來 n 行，每行給出三個整數$ x, y, k，\(中間用一個空格隔開，分別代表路口的坐標\) (x, y)$ 以及該路口公共場所的數量。同一坐標只會給出一次。

輸出格式

輸出一行，包含兩個整數，用一個空格隔開，分別表示能覆蓋最多公共場所的安裝地點方案數，以及能覆蓋的最多公共場所的數量。

輸入輸出樣例

輸入 #1 復制

1
2
4 4 10
6 6 20

輸出 #1 復制

1 30

說明/提示

對于\(100%\)的數據，\(1 \leq d \leq 20, 1 \leq n \leq 20，0 \leq x \leq 128 ， 0 \leq y \leq 128 , 0 < k \leq 1000000,1≤d≤20,1≤n≤20,0≤x≤128,0≤y≤128,0<k≤1000000\)

解析：

一道簡單的模擬題。

因為是\(129 \times 129\)的方陣，所以我們可以枚舉每一個點

然后以該點為中心開始對四周可以掃到的點累加和

我們開了兩個變量來記錄，

\(num\)記錄最大值的個數，\(ans\)記錄最大值，

有一個顯然的結論就是

我們更換最大值的時候就可以把num替換為1

與此值相同或者更大的數一定會在后面。

感性理解。

#include <cstdio> #include <iostream> #include <cmath> #include <algorithm> #include <cstring> #include <queue> #include <stack> #include <vector> #include <set> #define re register #define Max 130 int n,ans = 0,d,g[Max][Max],num; inline void init() {scanf("%d%d",&d,&n);int x,y,k;for(re int i = 1 ; i <= n ; ++ i)scanf("%d%d%d",&x,&y,&k),g[x][y] = k; } void work() {int max_place;for(re int i = 0 ; i <= 128 ; ++ i)for(re int j = 0 ; j <= 128 ; ++ j) {max_place = 0;for(re int a = -d ; a <= d ; ++ a)for(re int b = -d ; b <= d ; ++ b)if(a + i >= 0 && a + i <= 128 && b + j <= 128 && b + j >= 0)//判斷邊界情況max_place += g[a+i][b+j];if(max_place == ans) num++;if(max_place > ans) ans = max_place, num = 1;} } inline void print() {printf("%d %d",num,ans);} int main() {init();work();print();return 0; }

轉載于:https://www.cnblogs.com/handsomegodzilla/p/11442907.html

總結

以上是生活随笔為你收集整理的洛谷P2038 无线网络发射器选址的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。