题解：P11797 【MX-X9-T1】『GROI-R3』Another Me

2011hym · 2025-02-23 22:23:51 · 题解

解题思路

前言

这道题在我比赛的时候我原本想了几分钟没想到，结果一看同时增加直接笑了。

问题分析：

每次操作都是全局的，即对序列中的所有元素同时进行自增或自减。

我们需要找到一个操作次数 k，使得序列中的元素经过 k 次操作后，所有元素的绝对值的最大值最小。

观察：

设操作次数为 k，则操作后的序列为 a_i + k 或 a_i - k。

我们需要找到一个 k，使得 max(|a_i + k|) 或 max(|a_i - k|) 最小。

数学推导：

设 min_a 为序列中的最小值，max_a 为序列中的最大值。

如果我们进行 k 次全局自增操作，则序列变为 a_i + k。

如果我们进行 k 次全局自减操作，则序列变为 a_i - k。

我们需要找到一个 k，使得 max(|a_i + k|) 或 max(|a_i - k|) 最小。

最优解：

最优的 k 应该是使得序列中的最小值和最大值对称分布在 0 的两侧。

具体来说，我们可以通过调整 k，使得序列中的最小值和最大值关于 0 对称。

代码实现

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, minn = LLONG_MAX, maxn = LLONG_MIN, a[114], dif;
signed main() {
    // 输入
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        minn = min(minn, a[i]);
        maxn = max(maxn, a[i]);
    }
    // 计算最小值到 0 的距离
    dif = minn;
    maxn -= dif;
    minn = 0;
    // 计算最终结果
    if (maxn & 1) { // 判断是否为奇数
        cout << maxn / 2 + 1;
    } else {
        cout << maxn / 2;
    }
    return 0;
}

代码解释

输入：

读取 n 和序列 a_1, a_2, \dots, a_n。

同时计算序列中的最小值 minn 和最大值 maxn。

计算最小值到 0 的距离：

计算 dif = minn，即最小值到 0 的距离。

将序列中的所有元素减去 dif，使得最小值变为 0。

更新最大值 maxn = maxn - dif。

计算最终结果：

如果 maxn 是奇数，则输出 maxn / 2 + 1。

如果 maxn 是偶数，则输出 maxn / 2。