C++求前k大危险程度总和的高效算法实现

## 🎯 问题分析 这个问题本质是**在一个数组中找出前 k 个最大值并求和**。题目描述中“麻醉连续的 k 个人”其实有歧义，但从“危险程度最高的 k 个人”和“危险程度总和最高的 k 个人”来看，应该是**不要求连续**，而是选择任意 k 个危险程度最高的人。 > ⚠️ 注意：如果要求“连续 k 个人”的最大总和，那是另一个问题（滑动窗口），但题目明确说“危险程度最高的 k 个人”，所以按**前 k 大求和**处理。 --- ## 💡 解决方案对比 针对“找出前 k 大元素求和”问题，有几种常见方案： | 方法 | 时间复杂度 | 空间复杂度 | 适用场景 | |------|------------|------------|----------| | 排序后取前 k 个 | O(n log n) | O(1) | n 较小（≤1e5 可接受） | | 优先队列（最小堆） | O(n log k) | O(k) | k 较小，内存敏感 | | 快速选择（nth_element） | O(n) 平均 | O(1) | 数据量大，追求最优 | | 计数排序（利用值域） | O(n + max_a) | O(max_a) | a[i] ≤ 1000 时极快 | 由于 **a[i] ≤ 1000**，最大危险程度很小，可以采用**计数排序**，时间复杂度 **O(n)**，空间 **O(1000)**，这是最优解法。 --- ## 🛠️ 完整代码实现（C++） ### 方法一：计数排序（最优，推荐） ```cpp #include <iostream> #include <vector> using namespace std; int main() { int n, k; cin >> n >> k; vector<int> count(1001, 0); // 危险程度范围 1~1000 for (int i = 0; i < n; i++) { int val; cin >> val; count[val]++; } long long sum = 0; int remaining = k; // 从高到低累加 for (int val = 1000; val >= 1 && remaining > 0; val--) { int take = min(count[val], remaining); sum += (long long) val * take; remaining -= take; } cout << sum << endl; return 0; } ``` ### 方法二：优先队列（最小堆，通用） ```cpp #include <iostream> #include <vector> #include <queue> using namespace std; int main() { int n, k; cin >> n >> k; priority_queue<int, vector<int>, greater<int>> minHeap; // 最小堆 for (int i = 0; i < n; i++) { int val; cin >> val; minHeap.push(val); if (minHeap.size() > k) { minHeap.pop(); // 移除最小的，保持堆中为前 k 大 } } long long sum = 0; while (!minHeap.empty()) { sum += minHeap.top(); minHeap.pop(); } cout << sum << endl; return 0; } ``` --- ## 🔍 关键解释 - **计数排序法**：利用危险程度值域小（1~1000），用 `count[val]` 记录每种危险程度的人数，从高到低累加，直到取够 k 人。假设危险程度为 d 的人有 c 个，若取 t 个（t ≤ c），则贡献为 `d * t`。 - **最小堆法**：维护一个大小为 k 的最小堆，遍历时若堆大小超过 k，则弹出堆顶（当前最小元素）。最终堆中保留的就是前 k 大元素，累加即可。 - **边界注意**：`sum` 用 `long long`，因为 k 最大 100000，a[i] 最大 1000，总和最大可达 `1e8`，int 可能溢出（int 最大约 2.1e9，100000*1000=1e8 不溢出，但为保险仍建议用 long long）。 --- ## ⚡ 性能对比 对于 **n=100000, k=100000**（最坏情况）： - 计数排序：**O(n)**，约 10 万次操作，毫秒级 - 堆方法：**O(n log k)**，约 170 万次操作，稍慢但也可接受 - 排序法：**O(n log n)**，约 170 万次比较，也不差 但**计数排序**时间最优且常数极小，在 a[i] 值域受限时是最佳选择。 --- ## 📌 开发建议 1. **输入优化**：当 n 较大时，建议使用 `ios::sync_with_stdio(false); cin.tie(nullptr);` 加速输入。 2. **类型安全**：涉及大数累加时，优先使用 `long long` 或 `int64_t`。 3. **可扩展性**：如果危险程度值域变大（例如 1e9），计数排序不可行，应改用堆或快速选择。 4. **测试用例**：建议覆盖边界情况：k=1、k=n、所有值相同、值域极端（最小1、最大1000）。 5. **理解题目**：注意区分“连续 k 个”与“任意 k 个”，本题是后者。如果要求连续，则用滑动窗口求最大和，时间复杂度 O(n)。 --- ## 📚 相关扩展 - **快速选择算法**（`nth_element`）：C++ STL 中有 `std::nth_element`，可以 O(n) 平均找到第 k 大元素，然后用 `accumulate` 求和。 - **滑动窗口最大和**（若题目理解为连续 k 人）：用双指针维护窗口和，取最大值即可。 ```cpp // 若题意是连续 k 个人，则用此方法 int maxSum = 0, winSum = 0; for (int i = 0; i < n; i++) { winSum += a[i]; if (i >= k) winSum -= a[i - k]; if (i >= k - 1) maxSum = max(maxSum, winSum); } ``` --- ######[AI写代码神器 | 1432点数解答 | 2026-07-31 20:02:05]