G3013 [GESP202412 三级] 数字替换 题解

知识点：一维数组、最值、条件替换。

解题思路

先求原数组最小值lo和最大值hi，再遍历原数值：大于k替换成hi，小于k替换成lo，等于k保持不变。

为什么正确

极值在替换之前固定，逐个应用互斥比较分支与题目定义一致。

易错点

不能边改边重新求极值，否则结果可能依赖遍历顺序。

复杂度

时间O(n)，空间O(n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,k;
    cin>>n>>k;
    vector<int>a(n);
    for(int &x:a)cin>>x;
    int lo=*min_element(a.begin(),a.end()),hi=*max_element(a.begin(),a.end());
    for(int x:a)cout<<(x>k?hi:x<k?lo:x)<<" ";
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用6个自行生成的测试点。