数字替换 题解

题目分析

我们需要处理一个长度为 $n$ 的整数序列 $A$。给定一个整数 $k$，要求将序列中大于 $k$ 的数全部替换为原序列的最大值，将小于 $k$ 的数全部替换为原序列的最小值，等于 $k$ 的数保持不变。最终输出替换后的序列。

解题思路

题目要求依赖于原序列的两个全局属性：最大值和最小值。因此，我们需要分两步完成：

1. 求出整个序列的最大值与最小值。
   最大值用于替换大于 $k$ 的元素，最小值用于替换小于 $k$ 的元素。

2. 遍历序列，按照规则替换并输出。
   对于每个元素 $a_i$：

   • 若 $a_i>k$，输出最大值；
   • 若 $a_i<k$，输出最小值；
   • 若 $a_i = k$，直接输出 $a_i$。

算法说明

1. 读入 $n$ 和 $k$，以及长度为 $n$ 的序列 $A$（可以用数组存储）。
2. 初始化 $max\_value$ 和 $min\_value$ 为序列的第一个元素 $a_1$。
3. 遍历序列，用 max 和 min 函数更新最大值和最小值：
   • $max\_value = \max(max\_value, a_i)$
   • $min\_value = \min(min\_value, a_i)$
4. 再次遍历序列，对每个元素进行判断替换：
   • 如果 $a_i>k$，$a_i \leftarrow max\_value$
   • 如果 $a_i<k$，$a_i \leftarrow min\_value$
   • 否则 $a_i$ 不变
5. 按顺序输出替换后的序列，数字之间用空格分隔，行末换行。

时间复杂度分析

• 第一次遍历求最大最小值：$O(n)$。
• 第二次遍历替换并输出：$O(n)$。
• 总时间复杂度为 $O(n)$，在 $n \le 10^5$ 时完全可以运行通过。
• 空间复杂度：存储序列需要 $O(n)$ 的数组，也可以在读入时即时处理，但使用数组更直观，符合题目内存限制（$256$ MB）。

参考代码说明

以下参考代码使用 C++ 实现，步骤与上述算法一致。

cpp
复制
1#include <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5int a[100010];  // 全局数组，存储序列，长度大于等于 n 的最大值
6
7int main() {
8    int n, k;
9    cin >> n >> k;
10    
11    // 读入序列，下标从 1 到 n
12    for (int i = 1; i <= n; i++) {
13        cin >> a[i];
14    }
15    
16    // 初始化最大值和最小值为第一个元素
17    int max_value = a[1], min_value = a[1];
18    
19    // 第一次遍历：找出真正的最大值和最小值
20    for (int i = 1; i <= n; i++) {
21        max_value = max(max_value, a[i]);
22        min_value = min(min_value, a[i]);
23    }
24    
25    // 第二次遍历：替换并输出
26    for (int i = 1; i <= n; i++) {
27        if (a[i] > k) {
28            a[i] = max_value;          // 大于 k 替换为最大值
29        } else if (a[i] < k) {
30            a[i] = min_value;          // 小于 k 替换为最小值
31        }
32        // 等于 k 不处理
33        
34        // 输出，同一个循环内完成
35        if (i != n) {
36            cout << a[i] << " ";       // 数字间加空格
37        } else {
38            cout << a[i] << endl;      // 行末输出换行
39        }
40    }
41    return 0;
42}

代码细节

• 使用 max 和 min 函数简化比较，它们都包含在 <algorithm> 头文件中。
• 数组开在全局区，大小为 100010，是题目数据范围 $10^5$ 之上多出 $10$ 的常见写法，防止越界。
• 判断大小关系时使用 if-else if 结构，保证了等于 $k$ 的情况不会被错误替换。
• 输出格式与要求一致：除最后一个数字外，每个数字后跟一个空格；最后一个数字后跟换行符。

这道题主要考察基础循环和条件判断，是初学阶段的经典练习。希望题解能帮助你理解题意和实现方法。