刷题笔记合集🔗

告警抑制

问题描述

告警抑制，是指高优先级告警抑制低优先级告警的规则。高优先级告警产生后，低优先级告警不再产生。请根据原始告警列表和告警抑制关系，给出实际产生的告警列表。

• 不会出现循环抑制的情况。
• 告警不会传递，比如A->B,B->C，这种情况下A不会直接抑制C。但被抑制的告警仍然可以抑制其他低优先级告警。

输入格式

第一行为数字 ，表示告警抑制关系个数，。

接下来 行，每行是由空格分隔的两个告警ID，例如: id1 id2，表示id1抑制id2，告警ID的格式为：

大写字母+0个或者1个数字

最后一行为告警产生列表，列表长度[1,100]。

输出格式

真实产生的告警列表。

备注

告警ID之间以单个空格分隔。

样例输入

2
A B
B C
A B C D E

4
F G
C B
A G
A0 A
A B C D E

样例输出

A D E

A C D E

数据范围

• 
• 告警ID格式：大写字母+0个或者1个数字
• 告警产生列表长度： 长度

题解

这道题目主要考察对抑制关系的正确理解和处理。告警抑制是指高优先级告警出现后，会阻止低优先级告警的产生。

核心思路是：

1. 记录每个告警被哪些高优先级告警所抑制
2. 对于原始告警列表中的每个告警，判断是否应该实际产生

首先，需要建立一个映射关系，记录每个告警ID被哪些高优先级告警所抑制。例如，如果有关系"A B"，表示A抑制B，那么就需要记录B被A所抑制。

然后，遍历原始告警列表中的每个告警ID：

• 如果一个告警没有被任何高优先级告警抑制，那么它应该产生
• 如果一个告警被某些高优先级告警抑制，但这些高优先级告警都没有出现在原始告警列表中，那么它也应该产生
• 如果一个告警被某个高优先级告警抑制，且这个高优先级告警在原始告警列表中出现了，那么它不应该产生

需要特别注意的一点是，题目说明"告警不会传递"，即如果A抑制B，B抑制C，那么A不会直接抑制C。这意味着，如果原始告警列表中包含A和C但不包含B，那么C仍然会产生，因为B没有产生，不会抑制C。

这个问题可以通过构建一个哈希表或字典来高效解决，该数据结构记录了每个告警ID被哪些高优先级告警所抑制。

算法步骤：

1. 构建抑制关系映射，记录每个告警ID被哪些高优先级告警所抑制
2. 将原始告警列表转换为集合，便于快速查找
3. 遍历原始告警列表中的每个告警ID
4. 检查该告警是否被任何在原始告警列表中出现的高优先级告警所抑制
5. 如果不被抑制，则将其加入最终结果

时间复杂度分析：

• 构建抑制关系映射需要O(N)时间，其中N是抑制关系的数量
• 遍历原始告警列表和检查抑制关系需要O(M·K)时间，其中M是原始告警列表的长度，K是每个告警平均被抑制的高优先级告警数量
• 总体时间复杂度为O(N + M·K)，在最坏情况下为O(N + M²)，其中M ≤ 100，N ≤ 120，因此这个算法在给定的数据范围内是高效的

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

# 读取告警抑制关系的数量
n = int(input())

# 构建抑制关系映射
# suppress[id2] 存储能够抑制id2的所有告警id1的集合
suppress = {}
for _ in range(n):
    id1, id2 = input().split()
    if id2 not in suppress:
        suppress[id2] = set()
    suppress[id2].add(id1)

# 读取原始告警列表
alert_list = input().split()
alert_set = set(alert_list)

# 处理告警抑制逻辑
def process_alerts():
    result = []
    
    for alert_id in alert_list:
        # 检查该告警是否被任何出现在原始列表中的高优先级告警所抑制
        if alert_id not in suppress or not any(sup_id in alert_set for sup_id in suppress[alert_id]):
            result.append(alert_id)
    
    return result

# 获取实际产生的告警列表
actual_alerts = process_alerts()
print(" ".join(actual_alerts))

• Cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    // 构建抑制关系映射
    unordered_map<string, unordered_set<string>> suppress;
    for (in