机试题——村落基站建设

题目描述

假设村落以二叉树的形状分布，我们需要选择在哪些村落建设基站。如果某个村落建设了基站，那么它和它相邻的村落（包括本节点、父节点和子节点）也会有信号覆盖。目标是计算出最少需要建设的基站数。

输入描述

输入为一个完全二叉树的数组形式表示，从左到右、从上到下遍历。每个元素为 1 或 0，其中：

• 1 表示节点存在。
• 0 表示节点不存在。

节点数范围为 (1 < 节点数 < 8191)。

输出描述

输出为最少需要建设的基站数。

用例输入

输入：

1 1 1 1 0 1 1

输出：

2

说明：最少需要 2 个基站才能覆盖所有村落。

输入：

1 1 0 1 0 0 0

输出：

1

说明：只需要 1 个基站就能覆盖所有村落。

解题思路

1. 构建二叉树：

   • 使用数组表示的完全二叉树，通过递归构建二叉树结构。
   • 如果当前节点不存在（值为 0），则返回 nullptr。

2. 动态规划（DFS）：

   • 使用深度优先搜索（DFS）遍历二叉树，为每个节点计算三种状态：
     1. 在当前节点安装基站：子节点可以处于任何状态，因为当前节点的基站已经覆盖了本节点。
     2. 不在当前节点安装基站，依赖父节点的基站覆盖：子节点必须自己安装基站或依赖其子节点的基站覆盖。因为本节点不安装基站。
     3. 不在当前节点安装基站，依赖子节点的基站覆盖：至少有一个子节点必须安装基站，另一个子节点只能自己安装或者依赖他的子节点。
   • 对于每个节点，计算这三种状态的最小基站数，并返回结果。

3. 结果计算：

   • 根节点的最小基站数为在当前节点安装基站或依赖子节点安装基站的最小值。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <algorithm>
#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <set>
#include <list>
#include <sstream>
#include <bitset>
#include <stack>
#include <climits>
#include <iomanip>
#include <cstdint>
using namespace std;vector<int> tree; // 存储输入的二叉树数组struct node {int index; // 节点索引node* left; // 左子节点node* right; // 右子节点
};// 构建二叉树
node* build(int root) {if (root >= tree.size() || tree[root] == 0) return nullptr; // 如果节点不存在，返回nullptrnode* l = build(2 * root + 1); // 构建左子树node* r = build(2 * root + 2); // 构建右子树node* cur = new node; // 创建当前节点cur->index = root;cur->left = l;cur->right = r;return cur;
}// 深度优先搜索，计算每个节点的三种状态
vector<int> dfs(node* root) {if (root == nullptr) {return { INT_MAX / 2, 0, 0 }; // 非法节点，默认被覆盖}vector<int> l_dp = dfs(root->left); // 左子树的三种状态vector<int> r_dp = dfs(root->right); // 右子树的三种状态// 状态1：在当前节点安装基站// 子节点可以处于任何状态，因为当前节点的基站已经覆盖了它们int dp0 = *min_element(l_dp.begin(), l_dp.end()) + *min_element(r_dp.begin(), r_dp.end()) + 1;// 状态2：不在当前节点安装基站，依赖父节点的基站覆盖// 子节点必须自己安装基站或依赖其子节点的基站覆盖int dp1 = l_dp[2] + r_dp[2];// 状态3：不在当前节点安装基站，依赖子节点的基站覆盖// 至少有一个子节点必须安装基站int dp2 = min(l_dp[0] + min(r_dp[0], r_dp[2]),r_dp[0] + min(l_dp[0], l_dp[2]));return { dp0, dp1, dp2 };
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);string input;getline(cin, input); // 读取输入istringstream is(input);int num;while (is >> num) {tree.push_back(num); // 存储二叉树数组}node* root = build(0); // 构建二叉树vector<int> res = dfs(root); // 计算最小基站数cout << min(res[0], res[2]); // 输出结果return 0;
}