``` #include <vector> #include <climits> #include <algorithm> using namespace std; double calculateMaxAverage(vector<int>& scores) { int sum_known = 0; int count_known = 0; int min_known = INT_MAX; int max_known = INT_MIN; int missing = 0; for (int s : scores) { if (s == -1) { // 假设-1表示缺失值 missing++; } else { sum_known += s; count_known++; min_known = min(min_known, s); max_known = max(max_known, s); } } if (count_known == 0) return 0.0; // 无有效数据 if (missing == 0) { // 无缺失直接处理 return (sum_known - min_known) / (count_known - 1.0); } else { long total = sum_known + missing * max_known - min_known; int elements = count_known + missing - 1; return static_cast<double>(total) / elements; } }```说明 在你的历史课上，你得到了一个很长的作业。这个作业包含了N个题目（3 ≤ N ≤ 100,000），每个题目的成绩在0~10,000之间。 按照惯例，你的老师按照以下方式计算最终成绩：去掉你最低的一个成绩，然后将其余成绩的平均成绩作为最终成绩。但不幸的是，你的宠物牛“贝西”刚刚吃了前K个题目的答案！（1 ≤ K ≤ N-2） 经过你的一番解释，老师终于相信了你的故事，并且同意对你有答案的题目（没有被吃掉答案的题目）像之前一样给分——通过去掉最低的成绩（如果有多个最低成绩，则只去掉其中一个）并取剩余成绩的平均成绩。 根据这一成绩计算方案，请按升序输出所有可以使你最终成绩最高的K的值。 输入格式 第一行一个数N。 第二行N个数字，数字之间用空格隔开。 输出格式 若干行，升序输出所有符合的K的值。

<think>好的，我现在需要理解这个问题并给出解决方案。让我仔细看一下题目描述和给出的代码。 题目是说，学生有一个历史作业，包含N个题目，每个题目的成绩在0到10,000之间。但前K个题目的答案被牛吃了，所以这些成绩是缺失的。现在老师会处理剩下的N-K个成绩，也就是未被吃掉的部分，按照规则：去掉最低的一个成绩（如果有多个只去掉一个），然后剩下的取平均。我们的任务是找出所有可能的K值，使得最终的平均成绩最大，并且按升序输出这些K。 给出的代码是一个函数calculateMaxAverage，可能用来计算最大平均值的。我需要先理解这段代码的逻辑，然后根据问题描述，确定如何找到所有可能的K值。 首先，分析代码： 函数接收一个vector<int> scores，可能代表所有题目的成绩。其中，-1表示缺失值（也就是被吃掉的K个题目）。代码的逻辑如下： 1. 遍历所有分数，统计已知分数的总和sum_known，已知的数量count_known，已知的最小值min_known，最大值max_known，以及缺失的数量missing。 2. 如果没有已知数据，返回0.0。 3. 如果没有缺失值（即所有数据已知），那么计算方式是总和减去最小值，除以count_known-1。这符合题目中的规则：去掉最低的一个成绩，然后取平均。 4. 如果有缺失值（即missing>0），则总分为sum_known + missing * max_known（这里可能假设缺失的分数用最大值填充？），然后减去min_known，总元素数为count_known + missing -1。这部分的逻辑可能需要仔细推敲。 但问题是，题目中的K是前K个被吃掉，所以前K个的成绩是缺失的，而剩下的N-K个是已知的。而我们的任务是，对于不同的K值，计算对应的平均成绩，并找出所有使得平均最大的K值。 可能给出的代码中的逻辑与问题中的实际情况不符，或者需要重新理解。例如，问题中的K是吃掉前K个，剩下的N-K个中有可能有缺失吗？或者题目中的输入数据中的-1是否代表被吃掉的K个？ 这可能关系到如何处理不同的K值。例如，当选择不同的K值时，被吃掉的题目是前K个，剩下的N-K个是已知的。但原输入数据中，可能给出的scores数组中已经包含了所有题目的成绩，其中前K个被吃掉（视为-1？或者原数组中的-1可能表示被吃掉的K的位置？）。 或者，原代码中的处理可能与问题的实际输入方式不同。比如，原代码中的-1可能代表所有被吃掉的题目，而不管其位置是否是前K个。这可能意味着给出的代码可能并不直接对应问题中的输入条件，因为问题中的K决定了哪些位置被吃掉（前K个），而原代码可能处理的是任意位置的-1。 因此，这可能说明问题中的代码和题目描述之间存在不一致，或者需要重新理解问题。 或者，题目中的输入可能给出了所有题目的成绩，其中被吃掉的前K个题目被标记为-1，而其他的是已知的。例如，输入的第二行给出N个数字，其中前K个被设为-1，而剩下的可能已经被处理？或者说，输入的数据中的-1可能表示被吃掉的题目，而K的值等于前K个中有多少是-1？ 这可能有些混淆。所以需要仔细分析问题。 题目中的输入格式是第二行给出N个数字，其中每个数字代表对应题目的成绩。但被吃掉的前K个题目的成绩是无法获取的，所以输入中的这些位置的值可能已经被替换为-1？或者输入中的数值是已经处理后的，其中前K个可能被忽略？ 例如，假设输入的数组中的元素中，前K个是被吃掉的部分（也就是被当作缺失值处理），而剩下的N-K个是已知的。例如，当K=2时，输入数组的前两个元素被忽略，剩下的N-2个元素是已知的。但是问题中的输入可能给出的数组是完整的，其中前K个被当作缺失值，所以这些位置的值可能被替换为-1，或者在处理时，前K个被排除？ 可能题目中的输入数组中的元素中，前K个是缺失的，所以被标记为-1。例如，当输入数组的前K个是-1，其余的是已知的数值。但根据问题描述，当K被吃掉时，剩下的N-K个成绩是已知的。所以输入数组的结构应该是，前K个是-1，后面的N-K个是实际成绩。或者可能输入数组中的数值是包括所有题目，而不管是否被吃掉，但计算的时候，对于某个K，前K个被排除，剩下的N-K个中的数值是已知的，而原数组中可能包含-1？ 这可能需要更多的信息。例如，输入中的数组可能包含一些-1，表示被吃掉的题目。比如，当用户输入给出的数组中，前K个可能被吃掉，所以它们会被视为缺失值（即-1），而剩下的部分则是已知的数值？或者题目中的输入数组中的元素可能已经包含了所有已知的成绩，而前K个的位置会被忽略？ 此时，我可能需要重新理解问题中的输入输出要求。 根据问题描述中的输入格式： 第一行一个数N。 第二行是N个数字，用空格分隔。每个数字代表每个题目的成绩。其中，被吃掉的是前K个题目的答案，也就是前K个成绩视为缺失。所以，输入中的数值可能已经将前K个处理为-1？或者，输入中的数值是所有题目中的实际成绩，而不管是否被吃掉？ 或者，可能题目中的输入中的数组中的数值是未被吃掉的部分的成绩，而前K个题目被吃掉，所以它们的成绩是未知的，但剩下的N-K个题目是已知的，所以输入的数组中的数值可能包含这些剩下的N-K个成绩？ 此时，可能题目中的输入的第二行给出的N个数值中，前K个是已经被吃掉的，所以它们的值可能被忽略，而剩下的N-K个数值是已知的。例如，当K取某个值时，前K个数值被排除，剩下的N-K个数值被处理。因此，输入中的数组中的每个元素可能已经是实际成绩，但不同的K值对应不同的有效数据范围。 例如，当K=2时，有效的数据是数组的第3到第N个元素（假设索引从1开始），而前两个被排除。所以，对于每个可能的K值，我们需要从剩下的N-K个元素中选择，并计算其平均。 这可能更符合题目描述中的情况。例如，无论输入数组中前K个是什么，当计算K对应的分数时，前K个成绩被排除，剩下的N-K个成绩被使用。因此，在计算时，有效成绩是原数组中后N-K个元素，而前K个被忽略。 这样，原问题中的输入数组中的数值可能都是有效的，但不同的K值对应不同的有效区间。例如，对于K=0，有效数据是整个数组；而题目中的K的取值范围是1 ≤ K ≤ N-2。因此，对于每个可能的K值，我们需要取后N-K个元素作为有效成绩，然后计算这些成绩的平均值，去掉其中的最小值后的平均。 现在，我需要解决的问题是：给定一个数组，对于每个K（满足1 ≤ K ≤ N-2），取后N-K个元素，计算去掉其中一个最小值后的平均值。然后找出所有使得这个平均值最大的K值，并按升序输出这些K。 但原题中的输入可能有不同的情况，比如，输入中的某些元素可能已经是-1，但这可能不是问题中的情况。或者，可能输入中的每个元素都是已知的成绩，前K个被排除，剩下的作为有效成绩。 现在，回到原问题，正确的逻辑应该是： 当K被确定时，有效的成绩是原数组中后N-K个元素。例如，原数组有N个元素，取从第K+1到第N个元素作为有效数据。然后，在这部分数据中，去掉一个最小值，然后取平均。我们的目标是找出所有可能的K值（满足条件1 ≤ K ≤ N-2）使得这个平均最大。 例如，假设原数组是[5,3,1,4,2]，当K=2时，有效的数据是后3个元素，即[1,4,2]。去掉最小值1，剩下4和2，平均值是3。而如果K=1时，有效数据是后4个元素[3,1,4,2]，去掉最小值1，平均是 (3+4+2)/3=9/3=3。所以需要比较不同K对应的平均值，找出最大的那些。 因此，问题转化为：对每个可能的K，从原数组的后N-K个元素中找出最小值，然后计算总和减去最小值后的平均值（即总和减去min，除以（length-1））。 现在，如何高效地计算每个可能的K对应的这个值？ 原题中的N的范围是3 ≤ N ≤ 1e5，因此O(N^2)的算法无法通过，必须找到线性或O(N)的算法。 可能的思路是预处理每个可能的窗口的后缀的最小值，总和，然后对于每个可能的K（即窗口的大小是N-K），计算对应的总和和最小值，并计算平均值。 例如，当K取某个值时，对应的窗口大小是M = N-K。窗口的位置是数组的最后M个元素。因为对于不同的K，窗口大小M = N-K，而K的范围是1 ≤ K ≤ N-2 → M的范围是 2 ≤ M ≤ N-1。因为当K=N-2时，M=2，而当K=1时，M=N-1。但题目中的条件允许K的取值范围是1 ≤ K ≤ N-2，所以M的可能取值是2 ≤ M ≤ N-1。 所以，对于每个窗口大小M（其中M从2到N-1），我们需要计算最后M个元素的总和减去其中最小值，然后除以M-1。我们需要找到对应的K值（即K = N-M）使得这个平均最大。然后收集所有这样的K值，并输出它们按升序排列的结果。 现在，问题转化为：对于每个M=2,3,...,N-1，计算最后M个元素的总和和最小值，然后计算（总和 - min）/(M-1)。找出最大的这个值对应的所有M，然后将K=N-M转换为对应的K值，并按升序输出这些K。 例如，假设最大的平均出现在M=5和M=3，则对应的K=N-5和K=N-3，需要将这些K值排序。 现在，如何高效计算每个M对应的总和和最小值？ 对于总和，可以使用后缀和数组。例如，sum_suffix[i]表示从i到末尾的元素之和。那么，对于窗口大小M，最后M个元素的总和就是sum_suffix[N-M]（假设数组是0-based的话可能需要调整索引）。 对于最小值，可以用单调队列或预处理后缀最小值数组。例如，min_suffix[i]表示从i到末尾的最小值。同样，对于窗口大小M，最后M个元素的最小值是min_suffix[N-M]。 但预处理后缀的最小值数组可能不够，因为当窗口大小是M时，需要的是最后M个元素的最小值。而预处理每个位置i的后缀最小值是i到末尾的最小值，这可能无法直接得到某个窗口的末尾M项的最小值。例如，当窗口的位置是数组的最后M项，假设数组长度为n，那么它们的起始位置是n-M的位置。例如，数组0-based的话，起始位置是n-M，结束位置n-1。那么，min_suffix[n-M]即为该窗口的最小值。所以，只要预处理后缀最小值数组，其中min_suffix[i]表示从i到n-1的最小值。这样，对于窗口的最后M项，对应的起始位置是n-M，所以最小值是min_suffix[n-M]。 同样的，总和可以预处理后缀和数组，sum_suffix[i]表示从i到n-1的和。那么，最后M项的和是sum_suffix[n-M]。 这样，对于每个M，计算总和sum = sum_suffix[n-M]，最小值min_val = min_suffix[n-M]，那么平均值是 (sum - min_val)/(M-1)。 所以，预处理这两个数组后，我们可以在O(1)的时间内计算每个M对应的平均。 预处理sum_suffix和min_suffix的时间复杂度是O(N)，这样整个算法的时间复杂度是O(N)，符合题目中的约束。 现在，具体步骤： 1. 预处理后缀和数组sum_suffix，其中sum_suffix[i]表示从i到n-1的和。 sum_suffix[i] = arr[i] + sum_suffix[i+1] 初始时，sum_suffix[n] = 0。 计算方式：从后往前遍历数组。 2. 预处理后缀最小值数组min_suffix，其中min_suffix[i]表示从i到n-1的最小值。 min_suffix[i] = min(arr[i], min_suffix[i+1]) 初始时，min_suffix[n] = +infinity. 同样，从后往前遍历。 预处理完成后，对于每个可能的M（窗口大小），其中M的取值范围是2 <= M <= N-1，对应的K = N-M。注意，K的取值范围需要满足题目中的条件： 原题中的K的条件是1 ≤ K ≤ N-2 → K >=1 → N-M >=1 → M <= N-1. 同时，因为 M >=2 → K = N-M <= N-2. 所以，当M的取值范围是2 <= M <= N-1时，对应的K的取值是1 <= K <= N-2，符合题目中的条件。 因此，我们需要遍历所有M从2到N-1，计算对应的平均，然后找到最大的平均对应的所有M，然后转换为对应的K值。 例如，假设最大的平均对应的M是5和3，那么对应的K是N-5和N-3。需要将这些K按升序输出。 现在，如何高效处理这些步骤？ 举例说明： 假设输入数组是[3,1,9,5]，N=4。 那么，对于不同的K值： K=1 → M=4-1=3 → 窗口大小为3，取后3个元素，即[1,9,5]。总和是15，min是1。平均是(15-1)/(3-1) =14/2=7. K=2 → M=4-2=2 → 后两个元素是[9,5].总和14，min5.平均(14-5)/1=9. 所以最大的平均是9，对应的K=2。所以输出2。 所以，正确的结果是输出K=2。 现在，代码的大致思路是： 预处理sum_suffix和min_suffix数组。 遍历所有可能的M（从2到N-1）： sum = sum_suffix[n - M] min_val = min_suffix[n - M] avg = (sum - min_val) / (M-1) 记录最大的avg，并记录所有对应的M的K值（K = N - M）。 然后输出所有满足avg等于最大值的K值，按升序排列。 现在，如何处理数组的索引？ 假设原数组是0-based的，长度是n。那么，sum_suffix[i]是arr[i] + sum_suffix[i+1]。 例如，当数组长度是n=4，索引0~3： sum_suffix[0] = arr[0] + arr[1] + arr[2] + arr[3] sum_suffix[1] = arr[1] + arr[2] + arr[3] sum_suffix[2] = arr[2] + arr[3] sum_suffix[3] = arr[3] sum_suffix[4] = 0 同理，min_suffix数组： min_suffix[0] = min(arr[0], min_suffix[1]) min_suffix[1] = min(arr[1], min_suffix[2]) ... min_suffix[3] = arr[3] min_suffix[4] = +infinity. 当M=3时，对应的窗口是后3个元素，起始索引是n-M=4-3=1。即元素arr[1], arr[2], arr[3]。 sum_suffix[1]是这三个元素的和，min_suffix[1]是这三者的最小值。 所以，计算正确。 现在，编写代码的大致步骤： 读取N，然后读取数组arr（假设是0-based）。 预处理sum_suffix数组： sum_suffix的大小是n+1。sum_suffix[n] =0. for i从n-1 downto 0: sum_suffix[i] = arr[i] + sum_suffix[i+1] 预处理min_suffix数组： min_suffix的大小是n+1. min_suffix[n] = INF. for i从n-1 downto 0: min_suffix[i] = min(arr[i], min_suffix[i+1]) 然后，遍历M从2到n-1： start = n-M → 起始索引是start. sum_val = sum_suffix[start] min_val = min_suffix[start] avg = (sum_val - min_val) / (M-1) 记录最大的avg，并保存对应的K值（K =n-M）。 注意，当M的取值范围是2<=M<=n-1时，对应的K是n-M的取值范围是： 当M=2 → K =n-2. 当 M= n-1 → K= n - (n-1) =1. 所以，K的范围是1 ≤K ≤n-2，符合题目条件。 遍历所有M，计算avg，并记录最大的avg以及对应的K值。 最后，收集所有K值，排序后输出。 现在，如何处理可能的浮点数精度问题？例如，当两个不同的K值得到相同的avg，但计算时可能存在精度误差，该如何比较？ 例如，可能两个不同的M对应的avg值在数值上相等，但由于计算时的浮点误差，导致判断是否相等时出现问题。因此，可能需要以一定的精度进行比较，或者将所有计算转换为整数运算，避免浮点运算的误差。 但是，在本题中，所有数组元素都是整数，因此sum_val和min_val也是整数。计算avg=(sum_val -min_val)/(M-1)，这可能无法整除，所以必须用浮点数。 为了避免浮点精度问题，可以将所有avg值转换为分数形式，或者比较分子和分母的交叉乘积。例如，比较两个分数a=(s1-m1)/(m-1)和b=(s2-m2)/(m2-1)的大小，可以比较(s1-m1)*(m2-1) 与 (s2-m2)*(m1-1)。这样，可以避免浮点运算的精度问题。 因此，可能在计算时，保存avg的分子和分母的数值，或者在进行比较时，使用交叉相乘的方式比较大小，这样能避免浮点误差。 但这样会增加代码的复杂度。在本题中，由于数值范围可能较大，可能会溢出，但题目中的每个元素是0~1e4，而M可以是1e5，所以分子可能达到1e4*1e5=1e9，相乘时可能达到1e9*1e5=1e14，这在long long范围内是可以处理的。 因此，在代码中，可以用交叉相乘的方法来比较两个平均值的大小，这样就不会有浮点精度的问题。例如，当比较两个avg值avg1 = (s1 - m1)/(m1_len-1)和avg2=(s2 -m2)/(m2_len-1)，其中m1_len是M1，m2_len是M2，那么比较： (s1 -m1) * (m2_len -1) ? (s2 -m2) * (m1_len -1) 如果左边大，则avg1>avg2。 这样可以避免浮点数的精度问题，从而正确比较大小。 因此，在代码中，需要为每个M对应的avg值保存其分子和分母，或者直接记录分子和分母的数值，并比较时使用交叉相乘。 这可能更可靠，但会增加代码的复杂性。但考虑到题目中的N可能高达1e5，而每个M的循环是O(N)，所以必须高效处理。 因此，代码的大体思路： 预处理sum_suffix和min_suffix数组。 然后，遍历M从2到n-1： start =n-M sum_val = sum_suffix[start] min_val = min_suffix[start] current_avg_numerator = sum_val - min_val current_avg_denominator = M-1 保存这些数值，并比较大小。 现在，比较当前的最大avg，并记录对应的K值。 为了找到最大的avg，可以用交叉相乘的方式比较当前的最大值和当前候选值的大小。 初始时，max_numerator和max_denominator设为-1，或者初始化为一个很小的值。 然后，对于每个M： current_numerator = sum_val - min_val current_denominator = M-1 比较current_numerator * max_denominator和max_numerator * current_denominator： 如果前者大于后者，则current的avg更大。 例如，假设max对应的分数是max_numerator / max_denominator，当前分数是current_numerator / current_denominator。要比较这两个分数的大小： current_numerator * max_denominator > max_numerator * current_denominator → 则current更大。 等于的话则相等。 这样，可以避免浮点运算。 此外，当max_denominator为0时的情况需要处理，但根据题意，M>=2，所以current_denominator=M-1 >=1，所以不会出现分母为0的情况。 因此，在代码中，可以维护当前的最大分数，用分子和分母表示。并维护一个列表，保存所有达到这个最大分数的K值。 例如： 初始化max_num = -1，max_den=1。这样，初始的avg是-1，比其他可能的avg小。 然后，遍历每个M： 计算当前num和 den（sum_val - min_val， M-1）。 然后比较current_num * max_den 和 max_num * current_den： 如果前者大于后者 → 当前avg更大，更新max_num和max_den，并清空结果列表，添加对应的K。 如果等于 → 当前avg等于max，将对应的K加入结果列表。 如果小于 → 忽略。 这样，就能正确维护最大的avg以及对应的K值。 这样处理可以完全避免浮点运算的问题。 因此，代码的结构应该如下： 读取n，读取数组。 预处理sum_suffix和min_suffix. 计算max_num和max_den，初始化为-1/1. 遍历M从2到n-1: start = n-M sum_val = sum_suffix[start] min_val = min_suffix[start] current_num = sum_val - min_val current_den = M-1 if current_den ==0 → 不可能，因为 M>=2 → current_den >=1. compare current_num * max_den 与 max_num * current_den: if current_num * max_den > max_num * current_den: max_num = current_num max_den = current_den result_ks = [n-M] elif current_num * max_den == max_num * current_den: result_ks.append(n-M) else: pass 但需要注意，初始的max_num是-1，这可能问题。例如，当第一个处理的M对应的是current_num可能为负数吗？ 原题中的成绩是0到1e4，所以sum_val是总和，而min_val是其中的最小值。所以，sum_val - min_val >=0，因为sum_val是包括min_val在内的总和，所以 sum_val >= min_val. 当且仅当所有元素都等于min_val时，sum_val = min_val * M，此时sum_val - min_val = min_val*(M-1) ≥0，因为 M>=2 → M-1 >=1. 因此，current_num >=0，而current_den >=1. 所以，初始的max_num应该设置为一个比可能的最小值更小的数，比如初始设为-1，这样第一个处理的current_num >=0，那么current_num * max_den（max_den=1）等于 current_num *1 = current_num，而max_num * current_den = (-1)*current_den → 所以，比较current_num *1 > (-1)*current_den → 因为 current_den >=1，所以右边是负数，左边>=0 → 所以条件成立，更新max_num和max_den。 所以，初始化为max_num =-1，max_den=1是可行的。 这样，代码中的逻辑就能正确比较所有情况。 例如，假设当current_num=0时，比如sum_val = min_val，则current_num=0。此时，avg=0/(den)。这比之前的max_num=-1的情况大，所以会被选中。 因此，这样的初始化是正确的。 现在，编写代码： 例如，在C++中： 读取n和数组arr。 预处理sum_suffix和min_suffix。 然后遍历M=2到n-1： 计算start =n-M → 例如，当n=4，M=2 → start=4-2=2 → 数组的第2个元素（0-based）开始，取后两个元素，即索引2和3。 sum_val = sum_suffix[start] min_val = min_suffix[start] current_num = sum_val - min_val current_den = M-1 然后比较current_num *max_den 和 max_num *current_den. 根据比较结果更新max和result_ks。 最后，将result_ks排序，输出。 这样就能得到所有符合条件的K值，并按升序排列。 现在，测试这个逻辑是否正确。 例如，假设输入是： 4 3 1 9 5 预处理sum_suffix： n=4. sum_suffix[4] =0. sum_suffix[3] =5+0=5 sum_suffix[2] =9+5=14 sum_suffix[1]=1+14=15 sum_suffix[0]=3+15=18. min_suffix数组： min_suffix[4] =INF. min_suffix[3]=5 min_suffix[2]=min(9,5) =5. min_suffix[1] =min(1,5)=1. min_suffix[0]=min(3,1)=1. 现在，遍历M从2到3： 当M=2时： start=4-2=2 → 元素是索引2和3的元素，即9和5. sum_val =14（sum_suffix[2]=9+5=14） min_val=5 → 因为 min_suffix[2]=5. current_num =14-5=9. current_den=2-1=1. 比较：current_num=9，max_num初始是-1. 9*1 > (-1)*1 → 是的，所以更新max_num=9，max_den=1，result_ks=[4-2=2]. 当M=3时： start=4-3=1 → 元素是索引1、2、3 →1,9,5. sum_val=sum_suffix[1]=15. min_val=min_suffix[1]=1. current_num=15-1=14. current_den=3-1=2. 比较14*max_den (1) =14*1=14. max_num=9 → 9* current_den (2) =18. 14<18 → 所以不更新。 所以最大的avg是9/1=9，对应的K=2。输出2. 这与之前的例子结果一致。 另一个例子： 输入： 5 5 3 1 4 2 n=5. sum_suffix数组： sum_suffix[5]=0. sum_suffix[4] =2 → sum=2. sum_suffix[3] =4+2=6. sum_suffix[2] =1+6=7. sum_suffix[1] =3+7=10. sum_suffix[0] =5+10=15. min_suffix数组： min_suffix[5]=INF. min_suffix[4] =2. min_suffix[3] =min(4,2)=2. min_suffix[2] =min(1,2)=1. min_suffix[1] =min(3,1)=1. min_suffix[0] =min(5,1)=1. 现在，遍历M从2到4： M=2 → start=5-2=3 → 元素是4和2 → sum=6, min=2. current_num=6-2=4. den=1. 比较：4*1=4>初始-1 → 更新max_num=4，max_den=1，result_ks=[5-2=3]. M=3 → start=5-3=2 → 元素1、4、2 → sum=7, min=1. current_num=7-1=6. den=2. 比较6*1=6 vs4*2=8 →6<8 →不更新. M=4 → start=5-4=1 →元素3、1、4、2 →sum=10, min=1. current_num=10-1=9. den=3. 比较9*1=9 vs4*3=12 →9<12 →不更新. 所以，最大的avg是4，对应的K=3. 但是，当K=3时，剩下的2个元素是4和2，平均是（4+2-2）/(2-1)=4/1=4. 当K=2时，剩下的3个元素是1、4、2 → 去掉1，总和是6，平均3。但根据计算，当M=3时，对应的sum是7（1+4+2=7），减去min_val=1 →6，den=2 →3. 那为什么在M=2的时候，得到的是sum=6-2=4，den=1 →4. 所以，最大的avg是4，对应的K=3. 但根据之前的分析，这个例子中的另一个情况可能需要重新审视。例如，当K=3时，剩下的元素是后两个吗？ 原数组是5个元素，当K=3时，前三个被吃掉，剩下的后两个是4和2。因此，sum是4+2=6，去掉最小值2，剩下4 →平均4/1=4。这与计算结果一致。 所以，代码的输出是正确的。 现在，如何实现这个逻辑？ 在C++中，代码的大致结构： #include <vector> #include <climits> #include <algorithm> using namespace std; int main() { int n; cin >> n; vector<int> arr(n); for (int i=0; i<n; i++) { cin >> arr[i]; } vector<long long> sum_suffix(n+1, 0); vector<int> min_suffix(n+1, INT_MAX); for (int i =n-1; i >=0; i--) { sum_suffix[i] = arr[i] + sum_suffix[i+1]; min_suffix[i] = min(arr[i], min_suffix[i+1]); } long long max_num = -1; long long max_den = 1; vector<int> result_ks; for (int M=2; M <=n-1; M++) { int start = n - M; long long sum_val = sum_suffix[start]; int min_val = min_suffix[start]; long long current_num = sum_val - min_val; long long current_den = M-1; // 比较current_num / current_den 和 max_num / max_den if (current_den ==0) continue; // 不可能发生 if (max_num == -1) { // 初始情况 max_num = current_num; max_den = current_den; result_ks.clear(); result_ks.push_back(n - M); } else { // 交叉相乘比较 long long left = current_num * max_den; long long right = max_num * current_den; if (left > right) { max_num = current_num; max_den = current_den; result_ks.clear(); result_ks.push_back(n - M); } else if (left == right) { result_ks.push_back(n - M); } } } sort(result_ks.begin(), result_ks.end()); for (int k : result_ks) { cout << k << endl; } return 0; } 这样，代码应该能够正确处理所有情况。 现在，回到原问题中的给出的代码： 给出的代码中的逻辑可能与问题中的实际处理不同。例如，原代码中的处理方式可能试图将所有缺失值（标记为-1）替换为最大值，并减去最小值。这可能与问题中的条件无关，即原问题中的K决定了哪些元素被排除，而剩下的元素是已知的，没有缺失值。所以原代码中的处理可能与问题无关，或者说原代码可能不是正确的解法。 例如，原代码中的逻辑： sum_known是已知分数的总和，count_known是已知的数量。假设分数中的-1表示缺失值。 当没有缺失值时，返回（sum_known - min_known）/(count_known-1)。 当有缺失时，总分为sum_known + missing * max_known - min_known. 分母是count_known + missing -1. 这似乎假设缺失的分数被设置为最大值，然后总和减去原来的最小值，然后除以总元素数-1. 这可能与问题中的条件不同。例如，原问题中的K对应的窗口是后N-K个元素，这些元素是已知的，没有缺失值。而原代码中的逻辑是处理包含缺失值的数组，这可能与问题中的条件不符。因此，原代码可能不是正确的解法。 因此，原代码可能并不是正确的解答，而正确的方法应该如上述的预处理后缀数组的方法。 因此，用户给出的代码可能是一个错误的方法，而正确的解法需要按照上述思路处理。 因此，回答问题的时候，需要解释正确的解法，并可能指出原代码中的错误。 现在，总结答案： 问题要求对于每个K（吃掉前K个题目的答案），剩下的N-K个题目的成绩计算平均（去掉最低分一个后的平均），找出所有使平均最大的K值。 正确解法是预处理后缀和和后缀最小值数组，遍历可能的窗口大小M=N-K，计算对应的平均，并通过比较交叉乘积来找到最大值，记录对应的K值，排序后输出。 原代码中的处理方式可能错误地处理了缺失值的填充，而问题中的K对应的窗口中的成绩没有缺失值，所以原代码可能不适用于该问题。</think>以下是该问题的逐步解答： 我们需要找出所有使最终成绩最大的K值。关键思路是预处理后缀信息，通过比较每个可能K值对应的平均成绩来确定最优解。 ### 方法思路 1. **预处理后缀和与后缀最小值**： - `sum_suffix[i]` 表示从i到数组末尾的和 - `min_suffix[i]` 表示从i到数组末尾的最小值 2. **遍历可能的有效窗口大小M**： 对于每个M（即剩余题数=N-K），计算对应的平均成绩： - 总分 = 窗口总和 - 窗口最小值 - 平均分 = 总分 / (M-1) 3. **比较并记录最大值**： 用交叉相乘避免浮点误差，记录所有使平均分最大的K值。 ### 解决代码 ```cpp #include <iostream> #include <vector> #include <climits> #include <algorithm> using namespace std; int main() { int n; cin >> n; vector<int> arr(n); for (int i = 0; i < n; ++i) { cin >> arr[i]; } vector<long long> sum_suffix(n + 1, 0); vector<int> min_suffix(n + 1, INT_MAX); for (int i = n - 1; i >= 0; --i) { sum_suffix[i] = arr[i] + sum_suffix[i + 1]; min_suffix[i] = min(arr[i], min_suffix[i + 1]); } long long max_num = -1; long long max_den = 1; vector<int> result_k; for (int M = 2; M <= n - 1; ++M) { int start = n - M; long long sum_val = sum_suffix[start]; int min_val = min_suffix[start]; long long current_num = sum_val - min_val; long long current_den = M - 1; if (max_num == -1) { max_num = current_num; max_den = current_den; result_k.clear(); result_k.push_back(n - M); } else { long long left = current_num * max_den; long long right = max_num * current_den; if (left > right) { max_num = current_num; max_den = current_den; result_k.clear(); result_k.push_back(n - M); } else if (left == right) { result_k.push_back(n - M); } } } sort(result_k.begin(), result_k.end()); for (int k : result_k) { cout << k << endl; } return 0; } ``` ### 代码解释 1. **输入处理**：读取题目数量`n`和各题成绩。 2. **预处理后缀数组**： - `sum_suffix`存储从每个位置到末尾的总和。 - `min_suffix`存储从每个位置到末尾的最小值。 3. **遍历所有可能的窗口大小M**： 计算每个M对应的总分和最小值，并比较平均成绩。 4. **记录最优解**：通过交叉相乘比较避免浮点误差，记录所有使平均最大的K值。 5. **输出结果**：按升序输出所有符合条件的K值。 该方法的时间复杂度为$O(N)$，能够高效处理最大规模的数据。