1. 数组极值求解的基本方法在信息学奥赛中处理数组极值最大值和最小值是最基础也是最重要的技能之一。OpenJudge NOI 1.9 08题白细胞计数就是一个典型的考察数组极值处理的题目。我们先来看两种最常用的极值求解方法。第一种方法是同时保存极值和其下标。以最大值为例我们需要初始化一个临时变量mx来保存当前找到的最大值通常将其初始化为一个比数组中所有元素都小的值比如INT_MIN。同时还需要一个变量mi来记录当前最大值的下标。然后遍历数组每当遇到比mx更大的元素时就更新mx和mi的值。int mx INT_MIN; // 初始化为最小整数值 int mi -1; // 初始化下标 for(int i 0; i n; i) { if(a[i] mx) { mx a[i]; mi i; } }第二种方法更简洁只保存极值的下标。这种方法不需要额外的变量来存储极值本身而是通过下标来访问数组中的极值。初始时我们可以假设第一个元素就是极值然后遍历数组进行比较。int mi 0; // 假设第一个元素是最大值 for(int i 1; i n; i) { if(a[i] a[mi]) { mi i; } } // 最大值就是a[mi]这两种方法各有优缺点。第一种方法虽然需要多一个变量但可以直接获得极值而不用再次访问数组第二种方法代码更简洁但在后续使用极值时需要多一次数组访问。在实际编程中可以根据具体情况选择更适合的方法。2. 白细胞计数题目详解让我们深入分析OpenJudge NOI 1.9 08题白细胞计数的具体要求。题目大意是给定n个白细胞数量测量值需要排除最大值和最小值后求平均值然后找出所有有效测量值与平均值偏差的绝对值的最大值。这个题目考察了几个关键技能点找出数组中的最大值和最小值计算剩余元素的平均值计算绝对偏差并找出最大值在实现时有几个细节需要特别注意。首先是边界条件的处理比如当所有元素都相等时最大值和最小值实际上是同一个元素。这时如果简单地减去最大值和最小值来计算平均值就会出错。正确的做法是识别这种情况并进行特殊处理。if(max_i min_i) { // 所有元素相等的情况 ave (sum - a[max_i]) / (n - 1); // 只排除一个极值 }另一个需要注意的细节是浮点数的精度处理。题目要求输出保留两位小数这意味着我们需要使用fixed和setprecision来控制输出格式。cout fixed setprecision(2) ave dmax;在实际编码中我建议先处理输入数据然后分别找出最大值和最小值接着计算平均值最后遍历数组计算绝对偏差。这样的步骤清晰便于调试和修改。3. 统计处理的进阶技巧在解决类似白细胞计数这样的统计问题时除了基本的极值查找外还需要掌握一些进阶技巧。首先是高效计算部分元素平均值的方法。题目要求排除最大值和最小值后求平均我们可以先计算总和然后减去极值再除以n-2。double sum 0; for(int i 0; i n; i) { sum a[i]; } double ave (sum - a[max_i] - a[min_i]) / (n - 2);其次是绝对偏差的计算。我们需要遍历数组跳过最大值和最小值计算每个元素与平均值的差的绝对值并记录最大的那个。double dmax 0; for(int i 0; i n; i) { if(i ! max_i i ! min_i) { double diff fabs(a[i] - ave); if(diff dmax) { dmax diff; } } }这里使用了cmath库中的fabs函数来计算浮点数的绝对值。需要注意的是在比较浮点数时由于精度问题直接使用或!可能会出现问题。在实际比赛中通常会设置一个很小的epsilon值来判断两个浮点数是否相等。const double eps 1e-8; if(fabs(a - b) eps) { // 认为a和b相等 }4. 代码优化与常见错误在实现这类算法时有几个常见的优化点和易犯错误值得注意。首先是循环合并的优化。观察我们的解题步骤实际上需要对数组进行多次遍历一次找最大值一次找最小值一次求和还有一次计算偏差。在某些情况下我们可以合并这些循环。double sum 0; int max_i 0, min_i 0; for(int i 0; i n; i) { sum a[i]; if(a[i] a[max_i]) max_i i; if(a[i] a[min_i]) min_i i; }这样就把求和与查找极值的循环合并了减少了总的循环次数。不过要注意这种优化虽然能提高效率但可能会降低代码的可读性需要权衡利弊。另一个常见错误是初始化问题。在查找极值时如果初始化不当可能会导致错误的结果。比如如果将最大值的初始值设得不够小可能会漏掉一些实际更大的值。安全的做法是使用数组中的第一个元素作为初始值。// 安全的初始化方式 double mx a[0]; int max_i 0; for(int i 1; i n; i) { if(a[i] mx) { mx a[i]; max_i i; } }还有一个容易忽略的问题是数组越界。特别是在处理边界元素时要确保不会访问到数组之外的内存。在比赛中这种错误往往会导致程序崩溃或得到错误的结果。在实际编程中我建议先写出清晰正确的代码然后再考虑优化。过早的优化可能会引入难以发现的错误。同时要养成编写测试用例的习惯特别是针对边界条件的测试比如所有元素相等、数组只有两个元素等情况。
