题解

题目描述

给定一个长度为$n$的数组$a = [a_1, a_2, \dots, a_n]$，一次操作可以选择数组中的一个数，然后将其移除，剩余元素保持原顺序依次拼接。希望经过若干次操作后，使得数组中所有非空子数组的平均值均相同。
子数组的定义为从原数组中连续选取的一段元素（可以全选也可以部分选）。

题目分析与思路

• 问题本质：
  要使得一个数组中所有非空子数组的平均值均相同，必须要求数组中所有元素都相同。证明非常直观：

  1. 如果数组中元素均相同，则任意子数组的平均值都是这个相同的值。
  2. 如果数组中存在至少两个不同的数，则至少存在长度为$1$的子数组（即单个元素），这些子数组的平均值各不相同，从而不满足题目条件。

• 操作分析：
  因此，题目要求我们通过删除操作将原数组中的元素调整为全相同的形式。
  设选择使得剩余数组中所有元素均为$x$，则只需要保留原数组中所有值为$x$的元素，删除其它所有元素。
  为使删除次数最少，我们应选择原数组中出现次数最多的那个数。

• 公式推导：
  设数组长度为$n$，记某个数字的出现次数为$f$，最大出现次数为$f_{max}$。
  则需要删除的最少次数为

  $$\text{答案} = n - f_{max}.$$

代码分析

• 首先统计数组中每个数字的出现次数。
• 然后找到出现次数的最大值$f_{max}$。
• 最后答案即为$n - f_{max}$。
• 时间复杂度为$O(n)$，空间复杂度为$O(n)$，满足题目限制$n \le 2 \times 10^5$。

C++

#include <iostream>
#include <unordered_map>
#include <algorithm>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n; // 读入数组长度n
    unordered_map<int, int> freq;  // 用于统计每个数字出现次数的哈希表
    int x;
    int maxFreq = 0; // 记录最大频次

    for (int i = 0; i < n; i++) {
        cin >> x; // 读入数组元素a_i
        freq[x]++;
        maxFreq = max(maxFreq, freq[x]); // 更新最大频次
    }
    
    
    cout << n - maxFreq << "\n";
    return 0;
}

Python

# 读入数组长度n
n = int(input().strip())
# 读入数组元素，并转换成整数列表
a = list(map(int, input().split()))

# 使用字典统计每个数字出现的次数
freq = {}
maxFreq = 0  # 记录最大频次

for x in a:
    if x in freq:
        freq[x] += 1
    else:
        freq[x] = 1
    maxFreq = max(maxFreq, freq[x])  # 更新最大频次


print(n - maxFreq)

Java

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 读入数组长度n
        // 使用 HashMap 统计每个数字的出现次数
        HashMap<Integer, Integer> freq = new HashMap<>();
        int maxFreq = 0; // 记录最大频次
        
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt(); // 读入数组元素a_i
            // 更新 HashMap 中数字x的出现次数
            freq.put(x, freq.getOrDefault(x, 0) + 1);
            maxFreq = Math.max(maxFreq, freq.get(x)); // 更新最大频次
        }
        sc.close();
        
        
        System.out.println(n - maxFreq);
    }
}

题目内容

给定一个长度为 $n$ 的数组 $a$ ，定义一次操作

• 选择数组中的一个数，然后把这个数从数组中移除，其余元素按照原有顺序从前到后依次拼接，

现在她想要知道，自己最少需要操作几次，才能使得数组中所有非空学数组的平均值均相同。

子数组为从原数组中,连续的选择一段元素(可以全选，可以不选)得到的新数组。

输入描述

第一行输入一个整数$n(1≦n≦2×10^5)$,表示数组长度。

第二行输入$n$个整数$a_1,a_2,...,a_n (1≦a_i≦10^9)$代表数组。

输出描述

一个整数，表示最少操作次数。

样例1

输入

3
1 2 3

输出

2

说明

删除任意两个元素后，数组只剩下一个元素，此时只有一个非空子数组，一定满足题意。

样例2

输入

5
12111

输出

1

说明

唯一的方案是将第二个元素删除。