CSP-202203-1-未初始化警告

难点：时间复杂度

• 【核心】：统计输入的k组“赋值”中，右值不为0且未在先前作为左值出现过的次数
• 【坑!】本题直接通过暴力枚举时间复杂度很可能过不了

【90分思路】

• 定义数组 initialized 用来存储已经处理过的左值

• 如果右值不等于 0，检查其是否已经存在于 initialized 中

  • 遍历 initialized 数组
  • 如果找到右值已存在于数组中，则将标志 rightInInitializedArray 设置为真（1）
  • 如果在 initialized 数组中没有找到右值，则将 wrongAnswer 计数器增加1，表示发现了一个不符合预期的情况。

• 无论右值是否在 initialized 数组中找到，都会将当前左值添加到 initialized 数组中

• 时间复杂度O(k^2)：对于每个“赋值”都可能需要遍历整个已初始化的数组

#include <iostream>
using namespace std;
int main() {int n, k, wrongAnswer = 0, initializedNum = 0;cin >> n >> k;int initialized[100005] = {};for (int i = 0; i < k; i++){int left, right;cin >> left >> right;if (right != 0){bool rightInInitializedArray = 0;for (int j = 0; j < initializedNum; j++){// 右值是否在initializedif (right == initialized[j]){rightInInitializedArray = 1;break;}}if (!rightInInitializedArray) wrongAnswer++;}initialized[initializedNum] = left;initializedNum++;}cout << wrongAnswer;return 0;
}

【100分思路】

• 创建一个足够大的布尔数组，用于标记哪些数字已经作为左值出现过。这样，对每个右值检查，就可以在 O(1) 时间复杂度内完成。

#include <iostream>
using namespace std;int main() {int n, k, wrongAnswer = 0;cin >> n >> k;bool initialized[100001] = {}; for (int i = 0; i < k; i++) {int left, right;cin >> left >> right;if (right != 0 && !initialized[right]) {// 如果右值不为0且未在initialized中出现过wrongAnswer++;}// 记录左值initialized[left] = true;}cout << wrongAnswer;return 0;
}