题解

题目解析

• 输入输出：第一行输入两个正整数 $n$（序列长度）和 $k$（替换阈值）。第二行输入 $n$ 个整数表示序列 $A$。输出 $n$ 个整数，表示按照规则替换后的序列。
• 数据范围：$1 \le n \le 10^5$，$|a_i|, |k| \le 10^5$。数据规模允许线性扫描算法。
• 复杂度要求：时间复杂度 $O(n)$，需要两次线性扫描（一次求最值，一次替换）；空间复杂度 $O(n)$ 存储原序列。
• 算法知识点：线性扫描、最值查询、简单模拟

思路解析

1. 读取数据：读入序列长度 $n$、阈值 $k$ 以及长度为 $n$ 的整数序列。
2. 预处理最值：使用 max_element 和 min_element 分别找出序列中的最大值 $\textit{max\_val}$ 和最小值 $\textit{min\_val}$，作为后续替换的目标值。
3. 遍历替换：顺序扫描序列中的每个元素：
   • 若当前元素 $> k$，替换为 $\textit{max\_val}$；
   • 若当前元素 $< k$，替换为 $\textit{min\_val}$；
   • 若当前元素 $= k$，保持原值不变（隐含在逻辑中，不进入上述两个分支）。
4. 输出结果：处理每个元素后立即输出（或存储后统一输出），保持原序列顺序。

完整代码

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

const int MAXN = 1e5 + 10;
int arr[MAXN];

int main() {
    int n, k;
    cin >> n >> k;
    // 读入序列
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    // 关键步骤：找出序列中的最大值和最小值
    int max_val = *max_element(arr, arr + n);
    int min_val = *min_element(arr, arr + n);
    // 遍历替换并输出
    for (int i = 0; i < n; i++) {
        if (arr[i] > k) 
            arr[i] = max_val;      // 大于k替换为最大值
        else if (arr[i] < k) 
            arr[i] = min_val;      // 小于k替换为最小值
        // 等于k时保持原值，不做处理
        cout << arr[i] << " ";
    }
    return 0;
}