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

· · 题解

洛谷 P11797

题目传送门

题目大意

我们有一个整数序列 a_1, a_2, \dots, a_n ，通过进行任意次数的全局自增或全局自减操作，我们希望将所有元素的绝对值的最大值最小化。即，我们的目标是通过选择操作，使得操作后的序列中，绝对值最大的数尽可能小。

解题思路

  1. 为了达到最小化绝对值最大值的目标，可以考虑将所有数集中到 0 附近，就能得到最小的最大绝对值。

  2. 然后我们可以发现，上述操作的关心点只与 a 序列中的最大值和最小值有关，所以需要求出最大值和最小值。

  3. 接下来如何实现第一步呢？我们发现，最大值和最小值的差值就是整个数列的最大差值，所以直接将最大值和最小值的差值除以 2 就可以得到答案了。注意当差值为奇数的时候要上取整。

代码实现

#include <iostream>
#include <cstring>
#include <cstdio>
#define ll long long
using namespace std;
const int MAXN = 1e6 + 5;
const int INF = 1e9 + 100;
int n, a[MAXN];
int Min = INF, Max = -INF;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    for(int i = 1; i <= n; i ++) Min = min(Min, a[i]), Max = max(Max, a[i]); 
    if(Max >= 0 && Min <= 0) cout << (abs(Min) + Max) / 2 + (abs(Min) + Max) % 2;
    else cout << (Max - Min) / 2 + (Max - Min) % 2;

    return 0;

}

复杂度分析