美团笔试 美团笔试题 0412
笔试时间：2025年04月12日
历史笔试传送门：
第一题
题目：数组1.0
给定一个长度为 n 的数组 a。定义一次操作： 选择数组中的一个数，然后把这个数从数组中移除。其余元素按照原有顺序从前到后依次拼接。现在她想要知道，自己最少需要操作几次，才能使得数组中所有非空子数组的平均值均相同。子数组为从原数组中，连续的选择一段元素（可以全选、可以不选）得到的新数组。
输入描述
第一行输入一个整数 n(1 <= n <= 2 * 10^5)，表示数组长度。
第二行输入 n 个整数 a_1,a_2,.....,a_n \left(1 <= a_i <= 10^9 ) 代表数组。
输出描述
一个整数，表示最少操作次数。
样例输入
3
1 2 3
样例输出
2
说明：删除任意两个元素后，数组只剩下一个元素，此时只有一个非空子数组，一定满足题意。
参考题解
要使数组中所有非空子数组的平均值均相同，关键在于保证剩余元素满足特定条件。通过分析可知，唯一满足条件的剩余数组是所有元素相同或仅剩一个元素的情况。子数组特性： 若数组中存在不同元素，则子数组的平均值必然不同。例如，数组 [a, b] 的子数组平均值为 a、b、(a+b)/2，显然无法全部相同。 因此，只有剩余元素全相同或只剩一个元素时，才能满足所有子数组的平均值相同。操作目标：情况1：保留所有相同元素。此时需删除其他元素，操作次数为 n - max_count（max_count 是出现次数最多的元素的频次）。情况2：仅保留一个元素。操作次数为 n-1。 最终答案为两者的最小值 min(n - max_count, n-1)，但进一步观察可知，当 max_count ≥ 1 时，n - max_count ≤ n-1，因此答案简化为 n - max_count。
C++：[此代码未进行大量数据的测试，仅供参考]
#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
int n;
cin >> n;
unordered_map<int, int> cnt;
int mx = 0;
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
cnt[x]++;
mx = max(mx, cnt[x]);
}
cout << n - mx << endl;
return 0;
}
Java：[此代码未进行大量数据的测试，仅供参考]
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n];
Map<Integer, Integer> countMap = new HashMap<>();
int mx = 0;
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
countMap.put(a[i], countMap.getOrDefault(a[i], 0) + 1);
mx = Math.max(mx, countMap.get(a[i]));
}
System.out.println(n - mx);
}
}
Python：[此代码未进行大量数据的测试，仅供参考]
from collections import defaultdict n = int(input()) a = list(map(int, input().split())) cnt = defaultdict(int) mx = 0 for num in a: cnt[num] += 1 if cnt[num] > mx: mx = cnt[num] print(n - mx)
第二题
题目：小美的排列区间
小美拿到了一个数组 a，她用以下方式生成数组 b：初始b为空，随后，对于每个 a_i，依次将 1 到 a_i 这 a_i 个数添加到数组 b 的末尾。例如，对于a数组为[3,1,2]，生成的b数组为：[1,2,3,1,1,2]。现在小美想知道，b数组中有多少个连续子数组为排列？连续子数组为从原数组中，连续的选择一段元素（可以全选、可以不选）得到的新数组。长度为 n 的排列是由 1 ~ n 这 n 个整数、按任意顺序组成的数组，其中每个整数恰好出现一次。例如，{2,3,1,5,4} 是一个长度为 5 的排列，而 {1,2,2} 和 {1,3,4} 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。
输入描述
第一行输入一个正整数n，代表数组a的大小。
第二行输入n个正整数a_i，代表数组a的元素。
1 <= n <= 10^51 <= a_i <= 10^9
输出描述
一个整数，代表 b 数组的全部连续子数组中，为排列的数量。
样例输入
3
3 1 2
样例输出
7
说明：[1,2,3,1,1,2]有7个连续子数组是排列：3个长度为1的，2个长度为2的，2个长度为3的。
参考题解
数据比较大，不可能直接生成数组去统计，必须利用排列的特性和题目的特殊要求进行快速求解。块内贡献：每个块生成的子数组贡献的数量等于该块的长度，因为每个块的前m个元素恰好是1到m的排列。每个块生成的序列是[1,2,...,a_i]。这些序列的每个前缀子数组[1], [1,2], ..., [1,2,...,a_i] 都是排列。 例如，a_i=3 时贡献3个排列，a_i=1 时贡献1个。 总块内贡献是 sum_a = a[0] + a[1] + ... + a[n-1]。跨块贡献：对于每对相邻的块，计算可能形成排列的连续子数组数目。这些子数组必须满足最大值等于长度，并且元素总和为1到该长度的总和。当两个相邻块生成的序列连接时，可能形成跨越两个块的排列子数组。例如：前一个块的末尾部分是 [x, x+1, ..., a_i]后一个块的开头部分是 [1, 2, ..., y]组合后的子数组 [x, x+1, ..., a_i, 1, 2, ..., y] 可能是排列。子数组的长度必须等于其最大值。例如，长度为k的排列最大值是k。假设子数组跨越前块的末尾p个元素和后块的开头q个元素，总长度k = p + q。最大值只能是前块的末尾元素（即a_i），因此需满足 k = a_i。此时后块需要提供 q = a_i - p 个元素（且 q <= a_j）。p 的最小值：max(a_i - a_j, 1)p 的最大值：a_i - 1贡献数为 max(0, (a_i-1) - max(a_i - a_j, 1) + 1)。
C++：[此代码未进行大量数据的测试，仅供参考]
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<long long> a(n);
long long ans = 0;
for (int i = 0; i < n; ++i) {
cin >> a[i];
ans += a[i];
}
for (int i = 0; i < n - 1; ++i) {
long long a_i = a[i];
long long a_j = a[i + 1];
long long dn = max(a_i - a_j, 1LL);
long long up = a_i - 1;
if (dn <= up) {
ans += up - dn + 1;
}
}
cout << ans << endl;
return 0;
}
Java：[此代码未进行大量数据的测试，仅供参考]
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n];
long ans = 0;
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
ans += a[i];
}
for (int i = 0; i < n - 1; i++) {
int a_i = a[i];
int a_j = a[i + 1];
int dn = Math.max(a_i - a_j, 1);
int up = a_i - 1;
if (dn <= up) {
ans += (up - dn + 1);
}
}
System.out.println(ans);
}
}
Python：[此代码未进行大量数据的测试，仅供参考]
n = int(input
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
2025打怪升级记录，大厂笔试合集 C++, Java, Python等多种语言做法集合指南
