自动搬运

查看原文

来自洛谷，原作者为

	2011hym 暴力占据大脑，打表代替思考 | 寒鸦栖枯地，拿分靠暴力 | 空山不见人，爆0就红温

搬运于2025-08-24 23:10:19，当前版本为作者最后更新于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。