优化方案英语必修三_阿里云服务器租用多少钱一年_优化网哪个牌子好_整合营销传播的定义

问题描述

在游戏“小C大作战”中，每个角色都有一个能量值aiai​，能量大的角色可以击败能量小的角色，并获得对应的分数。每个角色被击败后，击败者可以获得bibi​得分。为了维持游戏平衡，每个角色最多只能击败mm个其他角色。请计算出每个角色最终可以获得的最大分数。

保证这些球的能量值两两不同。

---

测试样例

样例1：

输入：n = 5 ,m = 3 ,a = [1, 3, 5, 2, 4] ,b = [1, 2, 3, 4, 5]
输出：[0, 5, 11, 1, 7]

样例2：

输入：n = 4 ,m = 2 ,a = [10, 20, 30, 40] ,b = [2, 4, 6, 8]
输出：[0, 2, 6, 10]

样例3：

输入：n = 6 ,m = 1 ,a = [6, 12, 18, 24, 30, 36] ,b = [5, 10, 15, 20, 25, 30]
输出：[0, 5, 10, 15, 20, 25]

问题理解

1. 角色和能量值：每个角色都有一个能量值 a_i，能量值大的角色可以击败能量值小的角色。
2. 得分规则：击败一个角色可以获得对应的分数 b_i。
3. 击败限制：每个角色最多只能击败 m 个其他角色。
4. 目标：计算每个角色最终可以获得的最大分数。

数据结构选择

• 角色信息：我们可以将每个角色的能量值和得分存储在一个结构体或类中，方便后续处理。
• 排序：为了方便找到能量值比当前角色小的角色，我们可以对所有角色按能量值进行排序。

算法步骤

1. 初始化：创建一个数组来存储每个角色的最终得分，初始值为0。
2. 排序：按能量值对所有角色进行排序。
3. 计算得分：
   • 对于每个角色，从能量值比它小的角色中选择得分最高的 m 个角色进行击败。
   • 将这些角色的得分累加到当前角色的最终得分中。
4. 返回结果：返回每个角色的最终得分数组。

关键点

• 排序：排序的目的是为了方便找到能量值比当前角色小的角色。
• 选择得分最高的 m 个角色：可以使用优先队列（最大堆）来高效地选择得分最高的 m 个角色。

代码实现

#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;struct Character {int energy;int score;int index; // 用于记录原始索引
};vector<int> solution(int n, int m, vector<int> a, vector<int> b) {// 创建角色数组vector<Character> characters(n);for (int i = 0; i < n; ++i) {characters[i] = {a[i], b[i], i};}// 按能量值排序sort(characters.begin(), characters.end(), [](const Character& c1, const Character& c2) {return c1.energy < c2.energy;});// 初始化结果数组vector<int> result(n, 0);// 遍历每个角色，计算其最大得分for (int i = 0; i < n; ++i) {int currentEnergy = characters[i].energy;int currentIndex = characters[i].index;// 使用优先队列（最大堆）来选择得分最高的 m 个角色priority_queue<int> maxHeap;for (int j = 0; j < i; ++j) {if (characters[j].energy < currentEnergy) {maxHeap.push(characters[j].score);}}// 选择得分最高的 m 个角色int totalScore = 0;for (int k = 0; k < m && !maxHeap.empty(); ++k) {totalScore += maxHeap.top();maxHeap.pop();}// 更新结果数组result[currentIndex] = totalScore;}return result;
}int main() {cout << (solution(5, 3, {1, 3, 5, 2, 4}, {1, 2, 3, 4, 5}) == vector<int>{0, 5, 11, 1, 7}) << endl;cout << (solution(4, 2, {10, 20, 30, 40}, {2, 4, 6, 8}) == vector<int>{0, 2, 6, 10}) << endl;cout << (solution(6, 1, {6, 12, 18, 24, 30, 36}, {5, 10, 15, 20, 25, 30}) == vector<int>{0, 5, 10, 15, 20, 25}) << endl;return 0;
}

关键步骤解释

1. **结构体 Character**：用于存储每个角色的能量值、得分和原始索引。
2. 排序：按能量值对角色进行排序，以便后续计算得分。
3. 优先队列（最大堆）：用于选择得分最高的 m 个角色。
4. 计算得分：遍历每个角色，使用优先队列选择得分最高的 m 个角色进行击败，并累加得分。