美团笔试 美团笔试题 0823
笔试时间：2025年8月23日
往年笔试合集：
第一题
小美有 n 个长方形，第 i 个长方形的两条边长分别为 xi，yi；小美拥有一个仅包含第一象限的平面直角坐标系；小美希望将这 n 个长方形按顺序（可以旋转）放置在 x 轴上，不允许重叠，并且每个长方形放置后的高度不超过 m，保证 max(min(xi, yi)) ≤ m；请问，在满足上述条件的前提下，小美最少需要占用 x 轴的长度是多少？
输入描述
第一行输入两个整数 n, m（1 ≤ n ≤ 2×10⁵；1 ≤ m ≤ 10⁹），分别表示长方形的个数和允许的最大高度；接下来 n 行，每行输入两个整数 xi, yi（1 ≤ xi, yi ≤ 10⁹），分别表示第 i 个长方形的两条边长。
输出描述
输出一个整数，表示在每个长方形高度不超过 m 的情况下，所需占用的最短 x 轴长度。
样例输入
3 4
1 2
2 5
4 2
样例输出
8
参考题解
对于每个长方形，其边长为 x_i 和 y_i。在放置时，我们可以选择其中一条边作为高，另一条边作为长（即在 x 轴上的投影）。我们依次处理每个长方形，并为它选择最优的放置方式，使得它在 x 轴上占用的长度尽可能短。对于第 i 个长方形，边长为 x,y：如果 x 和 y 都大于 m： 这种情况在题目中被保证不会发生（保证 max(min(x_i,y_i)) <= m），因为这确保了每个长方形至少有一条边不大于 m。如果只有一条边大于 m：假设 xm 且 yleqm。此时，我们必须选择边长 y 作为高，因为 x 作为高会超过限制。因此，这个长方形在 x 轴上占用的长度就是 x。同理，如果 ym 且 xleqm，我们必须选择边长 x 作为高，占用的 x 轴长度为 y。如果 x 和 y 都不大于 m (xleqm 且 yleqm)：此时，无论用 x 还是 y 作为高，都满足条件。为了让占用的 x 轴长度最小，我们应该选择较短的那条边作为长度。因此，占用的长度为 min(x,y)。我们将每个长方形按上述规则计算出的最小长度累加起来，即可得到最终答案。
C++：
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
long long ans = 0;
for (int i = 0; i < n; i++) {
long long x, y;
cin >> x >> y;
if (x > m && y > m) {
continue;
} else if (x > m) {
ans += x;
} else if (y > m) {
ans += y;
} else {
ans += min(x, y);
}
}
cout << ans << "\n";
return 0;
}
Java：
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
long ans = 0;
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
long x = Long.parseLong(st.nextToken());
long y = Long.parseLong(st.nextToken());
if (x > m && y > m) {
// skip
} else if (x > m) {
ans += x;
} else if (y > m) {
ans += y;
} else {
ans += Math.min(x, y);
}
}
System.out.println(ans);
}
}
Python：
import sys def solve(): n, m = map(int, input().split()) ans = 0 for _ in range(n): x, y = map(int, sys.stdin.readline().split()) if x > m and y > m: pass elif x > m: ans += x elif y > m: ans += y else: ans += min(x, y) print(ans) solve()
第二题
需在仅依赖 numpy / pandas / scikit-learn 前提下，完成基于 DBSCAN 的异常检测器。 步骤说明 1. 读取数据：输入为含 train（二维列表，数值特征）、test（二维列表，特征维度与 train 相同，无标签，无监督场景）的 JSON 数据。 2. 预处理：将 train 与 test 按行拼接，用 StandardScaler 对所有特征做标准化（fit_transform 一次完成）。 3. DBSCAN 聚类：参数固定为 eps=0.3，min_samples=3，metric="euclidean"，algorithm="auto" 进行聚类。 4. 簇标签重映射：原本标签集合为 {-1, 0, 1, ...}，-1 为离群点；对非 -1 的簇，计算在标准化特征空间的质心 \(c_i\)，按质心第一维坐标从小到大排序得到顺序 \(\ell_0, \ell_1, \dots\)，重新赋值 \(\ell_0 \to 0\)，\(\ell_1 \to 1\)，…，离群点标签保持 -1 不变。 5. 结果输出：仅对 test 部分输出重新映射后的标签序列，以单行 JSON 数组输出。
输入描述
标准输入为一行 JSON，含 train、test 字段，数值为整数或浮点数，无空行。
输出描述
标准输出为一行 JSON 数组，长度等于测试样本数，逗号后有空格。
样例输入
{"train": [[0,0],[0,1,0],[5,5],[5,1.5],[5,10.0]],"test":[[0.05,0.05],[5.05,5.05],[9,0]]}
样例输出
[0, 1, -1]
参考题解
数据准备与合并 (Preparation)首先，代码读取输入的JSON数据，分离出train和test两部分。为了让所有数据点都在同一个空间中进行比较和聚类，它将train和test数据集合并。由于每个数据点的维度（向量长度）可能不同，代码会找到最长的维度，并将所有较短的数据点通过补0的方式填充到相同的长度，这被称为“Padding”。数据标准化与聚类 (Clustering)对合并后的整套数据进行标准化（StandardScaler）。这一步是为了消除不同特征（维度）之间量纲的影响，使得每个特征都能被公平地计算距离，这对DBSCAN这类依赖距离的算法至关重要。在标准化后的数据上执行核心的 DBSCAN 聚类算法，它会自动根据数据点的密度将它们划分成不同的簇，并将离群点标记为噪声（标签为-1）。标签重排序 (Reordering)这是整个代码中最关键的技巧。DBSCAN算法本身输出的簇标签（如簇0, 簇1, 簇2...）是不确定的，每次运行可能顺序不同。为了得到一个稳定且唯一的输出，代码通过以下方式对标签进行“规范化”处理：计算出每个非噪声簇的几何中心点（质心）。根据所有质心在第一个维度上的坐标值进行排序。按照这个新的排序顺序，将簇的标签重新命名为 0, 1, 2, ...。这样，无论运行多少次，空间位置最靠前的簇永远是0号，以此类推。
C++：
Java：
Python：
import json
import numpy as np
from sklearn.preprocessing import StandardScaler
from sklearn.cluster import DBSCAN
data = json.loads(input())
tlist = data.get('train', [])
tstlst = data.get('test', [])
ntsam = len(tlist)
full = tlist + tstlst
mxln = 0
if full:
mxln = max(len(row) for row in full)
pdlst = []
for row in full:
rw = row + [0] * (mxln - len(row))
pdlst.append(rw)
fulld = np.array(pdlst, dtype=float)
sc = StandardScaler()
scdt = sc.fit_transform(fulld)
dbscan = DBSCAN(eps=0.3, min_samples=3, metric="euclidean", algorithm="auto")
labs = dbscan.fit_predict(scdt)
unqlabs = np.unique(labs)
corlabs = sorted([label for label in unqlabs if label != -1])
mpplabs = np.copy(labs)
if corlabs:
ctrd = []
vcorelabs = []
for label in corlabs:
cluster_points = scdt[labs == label]
if cluster_points.shape[0] > 0:
centroid = cluster_points.mean(axis=0)
ctrd.append(centroid)
vcorelabs.append(label)
if ctrd:
ctrd = np.array(ctrd)
stdindi = np.argsort(ctrd[:, 0])
labmpp = {-1: -1}
for newlabs, oldlabsidx in enumerate(stdindi):
oldlabs = vcorelabs[oldlabsidx]
labmpp[oldlabs] = newlabs
mpplabs = np.array([labmpp.get(label, -1) for label in labs])
ans = mpplabs[ntsam:]
print(json.dumps(ans.tolist()))
第三题
给你两个正整数（x），（y），定义一个整数如果是特别的数，那么它一定满足以下条件至少其一：
- 它是（x）的整数倍。
- 它是（y）的整数倍。
- 它是（x）的因子。
- 它是（y）的因子。
给你一个整数（n），请你求出（1 ~ n）中有多少
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
2025打怪升级记录，大厂笔试合集 C++, Java, Python等多种语言做法集合指南
阿里云工作强度 727人发布
