首页 > 试题广场 >

小红的好数组

[编程题]小红的好数组

热度指数：967 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小红定义一个数组是好数组，当且仅当该数组中有且仅有一个元素和其他元素不同，剩余的所有元素相同。
例如，[2,2,2,5,2,2]是好数组。
小红拿到了一个数组，她可以进行若干次操作，每次操作可以使得一个元素加 1 或者减 1 。小红希望用尽可能少的操作次数使得该数组变成好数组，你能帮帮她吗？

输入描述:

第一行输入一个正整数 ，代表数组的大小。
第二行输入  个正整数 ，代表数组的元素。

输出描述:

一个整数，代表最小的操作次数。

示例1

输入

6
2 2 4 5 1 2

输出

说明

对第三个元素进行两次减1操作，对第五个元素进行一次加1操作即可。

示例2

输入

3
1 1 1

输出

说明

对第一个元素进行一次加1操作即可。

示例3

输入

2
10 100

输出

算法知识视频讲解

C/C++

alcttraz

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 1e5 + 10;

int n;
int a[N];
LL s[N];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    // 排序
    sort(a + 1, a + 1 + n);
    // 特判，处理所有元素相等的情况
    if (a[1] == a[n]) {
        puts("1");
        return 0;
    }
    // 计算前缀和
    for (int i = 1; i <= n; i++) {
        s[i] = s[i - 1] + a[i];
    }
    LL res = LONG_LONG_MAX;
    // 枚举哪一位作为diff
    for (int i = 1; i <= n; i++) {
        LL mid = n >> 1;
        // 计算剩余元素的中位数
        if (i <= mid) {
            mid++;
        }
        // 将数组分为两部分：[1,mid] 和[mid, n]
        LL sum = a[mid] * mid - s[mid] + s[n] - s[mid - 1] - (LL)a[mid] * (n - mid + 1);
        // diff不需要转换为mass
        sum -= abs(a[i] - a[mid]);
        res = min(res, sum);
    }
    printf("%lld\n", res);
    return 0;
}

编辑于 2026-02-20 15:18:20 回复(0)

Java