在一场算法比赛中，大家的wa次数天差地别。有直接ac的神牛，也有wa了100多次的GPT训练师。 出题人是一位追求极致公平的人，现在他想让大家的wa次数都一样。 出题人会一种魔法，可以选取任意 k 名同学，让他们的wa次数+1。 k 是由你给出，不可改变的一个整数。 这种魔法可以施展无限次。请问让所有同学wa次数相同的前提下，出题人可以选择的 k 最大值是多少? 输入格式 第一行一个整数 n(2≤n≤114514)，代表一共有 n 名同学参加了测试。 接下来给出 n 个整数，代表各同学的wa次数。保证这些整数不完全相同，并且值在 int 类型范围内。 输出格式 一个整数 k，代表能选择的最多同学数量。 输入输出样例 输入 #1复制运行 3 1 2 1 输出 #1复制运行 2 说明/提示 样例1中，选取 k 为2，让第一个和最后一个同学的wa次数 +1，得到2 2 2 使用C语言

### 关于调整wa次数的算法问题 此问题是典型的 **分配优化问题**，可以通过贪心算法来解决。以下是详细的分析和解决方案。 #### 问题描述 给定一组学生的 WA（Wrong Answer）次数列表 `w[]` 和一个整数 `k` 表示可以增加或减少每个学生 WA 次数的最大操作次数。目标是通过最多 k 次操作使得所有学生的 WA 次数相同，并返回满足条件的最大可能的 WA 值。 --- #### 解决方案设计 1. **核心思路** 使用二分查找配合贪心验证的方法解决问题。设定一个目标值 `target`，表示期望的所有学生的 WA 次数值。对于每一个 `target`，计算将其余 WA 值调整到 `target` 所需的操作总数。如果所需操作不超过 `k`，则尝试更大的 `target`；否则缩小范围[^1]。 2. **具体步骤** - 定义函数 `canAchieve(int target)` 来判断是否可以在至多 `k` 次操作下使所有 WA 值等于 `target`。 - 遍历数组 `w[]`，统计将每个元素调整到 `target` 的绝对差值之和。 - 如果总操作数小于等于 `k`，返回 true；否则返回 false。 - 利用二分查找，在 `[min(w), max(w)]` 范围内找到最大的可行 `target`。 3. **时间复杂度** - 单次调用 `canAchieve()` 时间复杂度为 O(n)，其中 n 是数组长度。 - 二分查找的时间复杂度为 O(log(max-w-min))，因此整体复杂度为 O(n log(max-w-min))。 --- #### 实现代码 ```c #include <stdio.h> #include <limits.h> // 函数声明 int canAchieve(int w[], int size, int target, int k); int main() { int n, k; scanf("%d %d", &n, &k); int w[n]; int min_w = INT_MAX, max_w = INT_MIN; // 输入数据并记录最小值和最大值 for (int i = 0; i < n; ++i) { scanf("%d", &w[i]); if (w[i] < min_w) min_w = w[i]; if (w[i] > max_w) max_w = w[i]; } int low = min_w, high = max_w, result = min_w; while (low <= high) { int mid = (low + high) / 2; if (canAchieve(w, n, mid, k)) { result = mid; // 更新结果为目标值 low = mid + 1; // 尝试更大值 } else { high = mid - 1; // 缩小范围 } } printf("Maximum possible equal value: %d\n", result); return 0; } // 辅助函数：判断能否达到指定的目标值 int canAchieve(int w[], int size, int target, int k) { long long total_operations = 0; for (int i = 0; i < size; ++i) { total_operations += abs(w[i] - target); if (total_operations > k) return 0; // 提前退出以提高效率 } return total_operations <= k ? 1 : 0; } ``` --- #### 结果解释 上述代码实现了基于二分查找和贪心策略的解决方案。其主要逻辑在于逐步逼近能够满足条件的最大目标值 `target`，并通过辅助函数 `canAchieve` 进行动态校验。 --- ###