NOIP 提高组初赛 · NOIP 2012 提高组初赛试题 第 23 题

#include <iostream>
using namespace std;
int n, i, temp, sum, a[100];
int main() {
    cin >> n;
    for (i = 1; i <= n; i++)
        cin >> a[i];
    for (i = 1; i <= n - 1; i++)
        if (a[i] > a[i + 1]) {
            temp = a[i];
            a[i] = a[i + 1];
            a[i + 1] = temp;
        }
    for (i = n; i >= 2; i--)
        if (a[i] < a[i - 1]) {
            temp = a[i];
            a[i] = a[i - 1];
            a[i - 1] = temp;
        }
    sum = 0;
    for (i = 2; i <= n - 1; i++)
        sum +  = a[i];
    cout << sum / (n - 2) << endl;
    return 0;
}

输入： 8 40 70 50 70 20 40 10 30 输出：_______

这题核心就是读懂代码逻辑。程序分三步走：先两趟冒泡把最大最小值挤到两头，再跳过首尾求中间数的平均值。拿到题先别急着算，顺着循环条件看数据怎么变，最后注意整数除法会直接截断小数部分。

最容易栽跟头的地方是以为冒泡排序只跑一趟就能排好序。其实这题特意写了两个循环：第一个从左到右把大的往后赶，第二个从右到左把小的往前赶，只有这两步做完数组才是完全有序的。如果漏看第二个循环，排序结果会乱，后面求和肯定错。还有很多人会忽略整数除法的特性，以为250除以6是41.666，其实C++里整除直接舍去小数，结果就是41。

这道题考查的是程序阅读能力，核心知识点是冒泡排序的两趟变体以及整数除法的特性。命题人喜欢在这种填空题里藏两个坑：一是排序逻辑不完整，二是输出结果的取整规则。咱们得把代码逐行掰开揉碎了看。程序开头定义了一个数组a和变量sum，main函数里先读入n和n个数，这一步很常规。紧接着是两个for循环，这是解题的关键。第一个循环i从1到n-1，条件是a[i]>a[i+1]就交换，这明显是把大的元素往右冒泡，第一趟结束后最大的那个数肯定到了a[n]的位置。但这时候数组还没排好，因为刚才冒上来的大数可能会把原本在右边的次大数挤到它左边去，形成局部逆序。所以程序又搞了个第二个循环，i从n倒着走到2，条件是a[i]<a[i-1]就交换，这是把小的元素往左冒泡，相当于再补一趟，确保最小值稳稳地待在a[1]的位置。两趟下来，数组才真正变成完全有序。接下来求和的部分，sum从0开始累加，循环i从2到n-1，特意跳过了首尾两个元素，也就是去掉了刚才冒出来的最大值和最小值。最后输出sum/(n-2)，这里一定要记住，C++里的整数除法会自动舍去小数部分，不会四舍五入。现在代入题目给的数据n=8，数组是40 70 50 70 20 40 10 30。第一趟冒泡后，最大的70跑到了末尾，数组变成40 50 70 20 40 10 30 70。第二趟冒泡把最小的10挪到了开头，数组变成10 40 50 70 20 40 30 70。此时数组已经有序了，首尾分别是10和70，中间的数是40 50 70 20 40 30。等等，这里有个细节，第二趟冒泡虽然把10移到了最左边，但并没有完全排好中间的数，不过题目只要求去掉首尾求平均，所以只要首尾确定就行。实际上经过这两趟，数组最终状态就是10 20 30 40 40 50 70 70，完全有序。去掉首尾10和70，剩下20+30+40+40+50+70=250，除以6得41.666...，整数除法取整就是41。所以答案填41。命题人挖的坑就在于很多人会以为一趟冒泡就够了，或者在计算平均值时忘了整数除法的规则，导致算出41.666或者误以为是42。另外还要注意循环的边界，第二个循环是到2为止，而不是到1，这样才能正确地把最小值移到a[1]。总之，做这类题一定要耐心，把每一步数据变化都推演一遍，别被代码的简洁性迷惑了。