题目链接

无线网络信号塔覆盖

题目描述

在一个 的城市网格中，分布着居民区、待激活的信号塔和空地。你需要选择激活一部分信号塔，以最大化所有居民区的总有效数据服务价值。

  • 覆盖规则: 一个位于 且半径为 的信号塔，可以覆盖位于 的居民区，当且仅当它们的欧几里得距离 。
  • 价值计算: 一个数据需求为 的居民区，若被 个信号塔同时覆盖，其有效价值为 。若未被覆盖 ()，价值为 。

目标:

  1. 计算可以实现的最大总数据服务价值。
  2. 在实现最大价值的前提下，所需激活的最少信号塔数量。

关键约束: 信号塔的总数不超过 11 个。

解题思路

本题的核心是决定激活哪些信号塔。由于信号塔的总数 非常小（），这强烈暗示我们可以通过枚举所有可能的信号塔激活组合来找到最优解。这正是 状态压缩 或 二进制枚举 的典型应用场景。

一个朴素的实现是，枚举 种状态，对每种状态都遍历一遍所有激活的塔和所有居民区，计算总价值。该算法的复杂度为 ，其中 是居民区数量。当 很大时，这个算法在 Python 等语言中可能会超时。

我们可以通过 预计算 来优化这个过程。

  1. 数据预处理与覆盖掩码

    • 遍历整个网格，分别存储所有信号塔和居民区的信息。假设有 个信号塔和 个居民区。
    • 创建一个数组 tower_masks，大小为 。tower_masks[j] 将是一个整数（位掩码），它的第 i 位为 1 表示第 i 座信号塔能够覆盖第 j 个居民区。
    • 我们花费 的时间预先计算并填充好 tower_masks 数组。在计算距离时，使用平方比较 (dr*dr + dc*dc <= radius*radius) 来避免开方运算。

  2. 优化的二进制枚举

    • 我们从 到 进行循环，每个 state 代表一种激活方案。
    • 初始化全局最优解：max_value = 0，min_towers_for_max = 0。

  3. 为每个状态计算总价值 (O(M))

    • 对于当前的 state： a. 计算激活塔数 current_towers，即 state 中 1 的个数 (popcount)。 b. 初始化当前总价值 current_value = 0。 c. 遍历所有居民区（从 到 ）： i. 找出当前状态下，既激活又覆盖了居民区 j 的塔。这可以通过位运算 state & tower_masks[j] 得到。 ii. 计算这些塔的数量 k，即 popcount(state & tower_masks[j])。 iii. 如果 ，将该居民区的有效价值 累加到 current_value。
    • 通过这种方式，我们可以在 的时间内计算出每个状态的总价值。

  4. 更新全局最优解

    • 计算出 current_value后，与 max_value 进行比较并更新，逻辑同前。

  5. 最终复杂度

    • 总时间复杂度为 ，这个效率足以通过所有测试用例。

代码

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

#ifdef _MSC_VER
#include <intrin.h>
#define __builtin_popcount __popcnt
#endif

using namespace std;

struct Tower {
    int r, c;
    long long radius_sq;
};

struct Resident {
    int r, c, demand;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int R, C;
    cin >> R >> C;

    vector<Tower> towers;
    vector<Resident> residents;
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) {
            int val;
            cin >> val;
            if (val < 0) {
                long long radius = -val;
                towers.push_back({i, j, radius * radius});
            } else if (val > 0) {
                residents.push_back({i, j, val});
            }
        }
    }

    int num_towers = towers.size();
    int num_residents = residents.size();

    vector<int> tower_masks(num_residents, 0);
    for (int j = 0; j < num_residents; ++j) {
        for (int i = 0; i < num_towers; ++i) {
            long long dr = towers[i].r - residents[j].r;
            long long dc = towers[i].c - residents[j].c;
            if (dr * dr + dc * dc <= towers[i].radius_sq) {
                tower_masks[j] |= (1 << i);
            }
        }
    }

    long long max_value = 0;
    int min_towers_for_max = 0;

    for (int state = 0; state < (1 << num_towers); ++state) {
        long long current_value = 0;
        
        for (int j = 0; j < num_residents; ++j) {
            int covering_mask = state & tower_masks[j];
            int k = __builtin_popcount(covering_mask);
            if (k > 0) {
                current_value += residents[j].demand / k;
            }
        }

        int current_towers = __builtin_popcount(state);
        if (current_value > max_value) {
            max_value = current_value;
            min_towers_for_max = current_towers;
        } else if (current_value == max_value) {
            min_towers_for_max = min(min_towers_for_max, current_towers);
        }
    }

    cout << max_value << " " << min_towers_for_max << endl;

    return 0;
}

import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;

class Tower {
    int r, c;
    long radiusSq;
}

class Resident {
    int r, c, demand;
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int R = sc.nextInt();
        int C = sc.nextInt();

        List<Tower> towers = new ArrayList<>();
        List<Resident> residents = new ArrayList<>();

        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                int val = sc.nextInt();
                if (val < 0) {
                    Tower t = new Tower();
                    t.r = i;
                    t.c = j;
                    long radius = -val;
                    t.radiusSq = radius * radius;
                    towers.add(t);
                } else if (val > 0) {
                    Resident res = new Resident();
                    res.r = i;
                    res.c = j;
                    res.demand = val;
                    residents.add(res);
                }
            }
        }

        int numTowers = towers.size();
        int numResidents = residents.size();

        int[] towerMasks = new int[numResidents];
        for (int j = 0; j < numResidents; j++) {
            Resident res = residents.get(j);
            for (int i = 0; i < numTowers; i++) {
                Tower tower = towers.get(i);
                long dr = tower.r - res.r;
                long dc = tower.c - res.c;
                if (dr * dr + dc * dc <= tower.radiusSq) {
                    towerMasks[j] |= (1 << i);
                }
            }
        }

        long maxValue = 0;
        int minTowersForMax = 0;

        for (int state = 0; state < (1 << numTowers); state++) {
            long currentValue = 0;
            
            for (int j = 0; j < numResidents; j++) {
                int coveringMask = state & towerMasks[j];
                int k = Integer.bitCount(coveringMask);
                if (k > 0) {
                    currentValue += residents.get(j).demand / k;
                }
            }
            
            int currentTowers = Integer.bitCount(state);
            if (currentValue > maxValue) {
                maxValue = currentValue;
                minTowersForMax = currentTowers;
            } else if (currentValue == maxValue) {
                minTowersForMax = Math.min(minTowersForMax, currentTowers);
            }
        }

        System.out.println(maxValue + " " + minTowersForMax);
    }
}

def main():
    R, C = map(int, input().split())
    grid = [list(map(int, input().split())) for _ in range(R)]

    towers = []
    residents = []
    for r in range(R):
        for c in range(C):
            val = grid[r][c]
            if val < 0:
                radius = -val
                towers.append({'r': r, 'c': c, 'radius_sq': radius * radius})
            elif val > 0:
                residents.append({'r': r, 'c': c, 'demand': val})
    
    num_towers = len(towers)
    num_residents = len(residents)

    tower_masks = [0] * num_residents
    for j in range(num_residents):
        resident = residents[j]
        for i in range(num_towers):
            tower = towers[i]
            dr = tower['r'] - resident['r']
            dc = tower['c'] - resident['c']
            if dr*dr + dc*dc <= tower['radius_sq']:
                tower_masks[j] |= (1 << i)

    max_value = 0
    min_towers_for_max = 0

    for state in range(1 << num_towers):
        current_value = 0
        
        for j in range(num_residents):
            covering_mask = state & tower_masks[j]
            k = bin(covering_mask).count('1')
            if k > 0:
                current_value += residents[j]['demand'] // k
        
        current_towers = bin(state).count('1')
        if current_value > max_value:
            max_value = current_value
            min_towers_for_max = current_towers
        elif current_value == max_value:
            min_towers_for_max = min(min_towers_for_max, current_towers)

    print(max_value, min_towers_for_max)

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法：状态压缩、二进制枚举、预计算
  • 时间复杂度：，其中 是网格尺寸， 是信号塔数量， 是居民区数量。
    • 预处理遍历网格需要 。
    • 预计算覆盖掩码需要 。
    • 主循环枚举 种状态，每种状态计算总价值需要 。
    • 总复杂度由枚举部分主导。
  • 空间复杂度：，用于存储信号塔、居民区的信息以及覆盖掩码数组。