题解 | #小红的好数组#

题目链接

题目描述

小红定义一个数组为“好数组”，当且仅当该数组中有且仅有一个元素与其他所有元素不同。例如，[2, 2, 5, 2, 2] 是一个好数组。

给定一个数组，每次操作可以使数组中的任意一个元素加 1 或减 1。目标是计算将原数组变为“好数组”所需的最少操作次数。

解题思路

一个“好数组”由两部分组成： $n-1$ 个值相同的“多数元素”和一个值不同的“唯一元素”。我们的目标是确定原数组中的哪些元素应该变成“多数元素”，哪个元素应该变成“唯一元素”，以及它们的最终值应该是多少，从而使总操作次数（即值的变化总量）最小。

为了最小化操作成本，一个关键的洞见是：要被塑造成“多数元素”的 $n-1$ 个原始数字，在数值上应该是最接近的。如果我们对原数组进行排序，那么最接近的 $n-1$ 个数必然是数组中的一个连续子段。

因此，经过排序后，只有两种选择“多数元素”的方案需要考虑：

选择排序后数组的前 $n-1$ 个元素 (s[0] 到 s[n-2]) 作为“多数元素”的原型。
选择排序后数组的后 $n-1$ 个元素 (s[1] 到 s[n-1]) 作为“多数元素”的原型。

对于任何一组数字，要将它们全部变为同一个值的最小操作成本，就是将它们全部变为这组数的中位数。

基于以上分析，我们的解题策略如下：

排序：首先对输入的数组 $a$ 进行升序排序，得到排序后的数组 $s$ 。
计算两种情况的成本：
- 情况一：选择 $s_0, s_1, \dots, s_{n-2}$ 作为“多数元素”组，而 $s_{n-1}$ 作为“唯一元素”。
  - 计算将 $s_0, \dots, s_{n-2}$ 全部变为它们的中位数所需的操作成本。这个中位数是 $s_{\lfloor(n-2)/2\rfloor}$ 。
  - 计算成本 $C_1 = \sum_{i=0}^{n-2} |s_i - s_{\lfloor(n-2)/2\rfloor}|$ 。
  - 根据“好数组”的定义，最终的多数值必须与唯一值不同。如果计算出的中位数恰好等于 $s_{n-1}$ ，我们就必须额外花费 1 的成本将唯一元素加 1 或减 1 来打破这个相等。所以，如果 $s_{\lfloor(n-2)/2\rfloor} == s_{n-1}$ ，则总成本为 $C_1 + 1$ 。
- 情况二：选择 $s_1, s_2, \dots, s_{n-1}$ 作为“多数元素”组，而 $s_0$ 作为“唯一元素”。
  - 计算将 $s_1, \dots, s_{n-1}$ 全部变为它们的中位数所需的操作成本。这个子数组的中位数是 $s_{1+\lfloor(n-2)/2\rfloor}$ 。
  - 计算成本 $C_2 = \sum_{i=1}^{n-1} |s_i - s_{1+\lfloor(n-2)/2\rfloor}|$ 。
  - 同样，如果中位数恰好等于 $s_0$ ，则总成本需要加 1。所以，如果 $s_{1+\lfloor(n-2)/2\rfloor} == s_0$ ，则总成本为 $C_2 + 1$ 。
最终答案：比较两种情况的总成本，取较小者即为问题的最优解。

该算法的主要计算开销在于排序，因此总时间复杂度是 $\mathcal{O}(n \log n)$ 。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <cmath>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    sort(a.begin(), a.end());

    if (n <= 2) {
        if (n == 2 && a[0] == a[1]) {
            cout << 1 << endl;
        } else {
            cout << 0 << endl;
        }
        return 0;
    }

    // 情况一: s[0]...s[n-2] 成为多数元素
    long long cost1 = 0;
    long long median1 = a[(n - 2) / 2];
    for (int i = 0; i <= n - 2; ++i) {
        cost1 += abs(a[i] - median1);
    }
    if (median1 == a[n - 1]) {
        cost1++;
    }

    // 情况二: s[1]...s[n-1] 成为多数元素
    long long cost2 = 0;
    long long median2 = a[1 + (n - 2) / 2];
    for (int i = 1; i <= n - 1; ++i) {
        cost2 += abs(a[i] - median2);
    }
    if (median2 == a[0]) {
        cost2++;
    }

    cout << min(cost1, cost2) << endl;

    return 0;
}

import java.util.Scanner;
import java.util.Arrays;
import java.lang.Math;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextLong();
        }

        Arrays.sort(a);

        if (n <= 2) {
            if (n == 2 && a[0] == a[1]) {
                System.out.println(1);
            } else {
                System.out.println(0);
            }
            return;
        }

        // 情况一: s[0]...s[n-2] 成为多数元素
        long cost1 = 0;
        long median1 = a[(n - 2) / 2];
        for (int i = 0; i <= n - 2; i++) {
            cost1 += Math.abs(a[i] - median1);
        }
        if (median1 == a[n - 1]) {
            cost1++;
        }

        // 情况二: s[1]...s[n-1] 成为多数元素
        long cost2 = 0;
        long median2 = a[1 + (n - 2) / 2];
        for (int i = 1; i <= n - 1; i++) {
            cost2 += Math.abs(a[i] - median2);
        }
        if (median2 == a[0]) {
            cost2++;
        }

        System.out.println(Math.min(cost1, cost2));
    }
}

import sys

def solve():
    n = int(sys.stdin.readline())
    a = list(map(int, sys.stdin.readline().split()))
    
    a.sort()

    if n <= 2:
        if n == 2 and a[0] == a[1]:
            print(1)
        else:
            print(0)
        return

    # 情况一: s[0]...s[n-2] 成为多数元素
    cost1 = 0
    median1 = a[(n - 2) // 2]
    for i in range(n - 1):
        cost1 += abs(a[i] - median1)
    if median1 == a[n - 1]:
        cost1 += 1

    # 情况二: s[1]...s[n-1] 成为多数元素
    cost2 = 0
    median2 = a[1 + (n - 2) // 2]
    for i in range(1, n):
        cost2 += abs(a[i] - median2)
    if median2 == a[0]:
        cost2 += 1
        
    print(min(cost1, cost2))

solve()

算法及复杂度

算法：排序 + 中位数 + 分情况讨论
时间复杂度： $\mathcal{O}(n \log n)$ ，主要由数组排序的开销决定。
空间复杂度： $\mathcal{O}(n)$ 或 $\mathcal{O}(\log n)$ ，取决于排序算法所使用的空间。