C++实现戴夫后院抵御僵尸的植物选择策略

```cpp #include <iostream> #include <vector> #include <algorithm> #include <unordered_map> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin >> T; while (T--) { int n; cin >> n; vector<int> s(n); for (int i = 0; i < n; i++) { cin >> s[i]; } vector<int> t(n); for (int i = 0; i < n; i++) { cin >> t[i]; } // 分离普通植物和特殊植物 vector<int> normal, special; for (int i = 0; i < n; i++) { if (t[i] == 0) { normal.push_back(s[i]); } else { special.push_back(s[i]); } } // 对普通植物排序 sort(normal.begin(), normal.end()); // 统计特殊植物的数量 int specialCount = special.size(); // 使用哈希表记录每个攻击力值 unordered_map<int, bool> exists; for (int val : normal) exists[val] = true; for (int val : special) exists[val] = true; // 贪心选择普通植物 int selectedNormal = 0; for (int val : normal) { bool canSelect = false; // 检查是否存在特殊植物 if (specialCount > 0) { canSelect = true; } // 检查是否存在其他植物满足整除条件 if (!canSelect) { // 检查是否存在已选的普通植物满足条件 for (int other : normal) { if (other == val) continue; if (exists[other] && (val % (other + 1) == 0)) { canSelect = true; break; } } } // 检查是否存在特殊植物满足条件 if (!canSelect) { for (int sp : special) { if (val % (sp + 1) == 0) { canSelect = true; break; } } } if (canSelect) { selectedNormal++; // 标记当前植物已被选择 exists[val] = true; } } // 特殊植物总是可以被选择 int result = specialCount + selectedNormal; cout << result << "\n"; } return 0; } ``` 代码说明： 1. 数据结构： - 使用`vector<int>`存储普通植物和特殊植物的攻击力 - 使用`unordered_map`记录存在的植物攻击力值 2. 算法逻辑： - 特殊植物（t=1）总是可以被选择 - 普通植物需要满足条件：存在已选植物j使得`s[i] % (s[j] + 1) == 0` - 采用贪心策略选择普通植物 3. 优化： - 对普通植物排序便于处理 - 使用哈希表快速检查植物是否存在 - 优先检查特殊植物是否满足条件 4. 时间复杂度： - 每组数据O(n²)最坏情况，适合n≤1000的数据规模 注意： 这是一个贪心解法，对于某些特殊测试用例可能不是最优解。如果数据规模更大或需要精确最优解，可能需要使用图论或动态规划方法。 ######[AI问答 | 773点数解答 | 2026-01-19 19:20:57]