C++ 求解数组操作后最大 |R - Ai| 的最小值问题

这个问题要求我们找到一个整数 \( R \)，使得在进行了任意次数的 \( A_i \gets A_i - T \) 操作后，最大的 \( |R - A_i| \) 尽可能小。我们需要找到这个最小的最大值。 方法思路 1. 问题分析：每次操作可以将任意元素 \( A_i \) 减去 \( T \) 的任意次数。这意味着每个元素 \( A_i \) 最终可以表示为 \( A_i - k_i \times T \)，其中 \( k_i \) 是非负整数。我们的目标是选择一个 \( R \) 使得所有调整后的 \( A_i \) 与 \( R \) 的最大绝对差最小化。 2. 关键观察：调整后的每个 \( A_i \) 可以看作是在模 \( T \) 下的余数，即 \( A_i \mod T \)。所有调整后的 \( A_i \) 可以表示为 \( r_i \), 其中 \( r_i = A_i \mod T \)。如果所有 \( r_i \) 相同，那么选择 \( R = r_i \) 会使最大绝对差为 0。 3. 处理不同余数：如果余数不同，我们需要找到一个 \( R \) 使得所有 \( r_i \) 与 \( R \) 的最大绝对差最小。这相当于在模 \( T \) 的环上找到一个点 \( R \)，使得最远的 \( r_i \) 到 \( R \) 的距离最小。这个最小最大值实际上是环上的最小直径，即 \( \lceil (max\_r - min\_r) / 2 \rceil \)。 解决代码 ```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int N, T; cin >> N >> T; vector<int> A(N); for (int i = 0; i < N; ++i) { cin >> A[i]; } vector<int> mods(N); for (int i = 0; i < N; ++i) { mods[i] = A[i] % T; } int min_mod = *min_element(mods.begin(), mods.end()); int max_mod = *max_element(mods.begin(), mods.end()); int max_diff; if (max_mod >= min_mod) { max_diff = (max_mod - min_mod + 1) / 2; } else { // This case shouldn't happen since mods are in [0, T-1] max_diff = 0; } cout << max_diff << endl; return 0; } ``` 代码解释 1. 输入处理：读取整数 \( N \) 和 \( T \)，以及数组 \( A \)。 2. 计算模值：计算每个元素 \( A_i \) 对 \( T \) 取模的结果，存储在 `mods` 数组中。 3. 查找极值：找到 `mods` 数组中的最小值和最大值。 4. 计算最小最大绝对差：根据模值的极差计算可能的最小最大绝对差。如果所有模值相同，差为0；否则，差为极差的一半向上取整。 5. 输出结果：打印计算得到的最小最大绝对差。 注意事项 1. 模运算处理：确保所有模值在 \( [0, T-1] \) 范围内，避免负数或超出范围的值。 2. 极差计算：当模值的最小值和最大值相等时，最大绝对差为0，因为所有元素可以调整到同一值。 3. 边界情况：处理 \( T = 1 \) 时所有模值为0，此时最大绝对差自然为0。 额外逻辑点 - 确保所有模值计算正确，避免负数模值出现。 - 当模值的极差为0时，直接输出0，无需进一步计算。 - 极差计算时注意整数除法的向上取整处理。 ######[AI写代码神器 | 847点数解答 | 2025-05-24 22:21:43]