初一某班有n位同学，学号1～n，新学期开始大家相互不认识，两两之间的好感度均为0。 这一个学期内发生了很多事情，影响着人与人之间的好感度。例如当a对b做了好事，b对a的好感度会增加；当a对b做了坏事，b对a的好感度会减少。 老师希望能在每件事情发生后，统计当下同学间好感度的最大值，你能帮他完成吗？ 注意：好感度不是相互的，a对b的好感度可以不等于b对a的好感度。

要解决这个问题，我们可以使用一个二维数组来存储每位同学之间的当前好感度，并在每次事件发生后更新这个数组。我们需要维护一个变量来记录当前的最大好感度。 具体步骤如下： 1. 初始化一个 \( n \times n \) 的二维数组 `goodwill`，其中 `goodwill[i][j]` 表示第 \( i \) 位同学对第 \( j \) 位同学的好感度。初始时所有好感度为0。 2. 初始化一个变量 `max_goodwill` 为0，用于记录当前的最大好感度。 3. 对于每个事件： - 如果是做好事，增加相应的好感度。 - 如果是做坏事，减少相应的好感度。 - 更新 `max_goodwill`，确保它始终是当前的最大好感度。 4. 每次事件处理完后，输出当前的最大好感度。 下面是一个Python代码实现： ```python def update_goodwill(n, events): # 初始化好感度矩阵 goodwill = [[0 for _ in range(n)] for _ in range(n)] max_goodwill = 0 for event in events: action, a, b, value = event a -= 1 # 转换为0索引 b -= 1 # 转换为0索引 if action == "good": goodwill[b][a] += value elif action == "bad": goodwill[b][a] -= value # 更新最大好感度 max_goodwill = max(max_goodwill, goodwill[b][a]) # 输出当前的最大好感度 print(max_goodwill) # 示例输入 n = 5 events = [ ("good", 1, 2, 10), ("bad", 2, 1, 5), ("good", 3, 4, 15), ("good", 4, 3, 20), ("bad", 1, 3, 2) ] update_goodwill(n, events) ``` 解释 - `goodwill` 是一个 \( n \times n \) 的二维数组，初始化为0。 - `max_goodwill` 用于记录当前的最大好感度。 - `events` 是一个列表，每个元素是一个元组，表示一个事件。元组的形式为 `(action, a, b, value)`，其中 `action` 是字符串 "good" 或 "bad"，`a` 和 `b` 是同学的学号（从1开始），`value` 是好感度的变化值。 - 在每个事件中，根据 `action` 更新 `goodwill` 数组，并更新 `max_goodwill`。 - 每次事件处理完后，输出当前的最大好感度。 这个算法的时间复杂度主要取决于事件的数量和每次事件的处理时间。每次事件的处理时间是常数级别的，因此总体复杂度是 \( O(m) \)，其中 \( m \) 是事件的数量。 [2024-10-17 16:17:46 | AI写代码神器 | 648点数解答]