饿了么笔试 饿了么笔试题 0412
笔试时间：2025年04月12日
历史笔试传送门：
第一题
题目：小红的小苯题
小红拿到了一个正轮数x，小苯希望小红找到一个正整数y，满足x⊕y既是x的因子，也是y的因子，你定帮帮小红吗?在这里，⊕表示位运算中的按位异或操作。
输入描述
如果存在解，请输出一个正整数y(1≤y≤10^18)，代表询问的答案。如果无解，请输出-1.如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。
样例输入
6
样例输出
4
说明：由于6⊕4=2，而2同时是4和6两个数字的因数。所以，6是一个正确的答案。
参考题解
因为1是所有数字的因子，所以直接让y=x^1，凑出1即可。
C++：[此代码未进行大量数据的测试，仅供参考]
#include <bits/stdc++.h>
using namespace std;
int main() {
long long x;
if(!(cin >> x)) return 0;
if (x == 1) {
cout << -1 << "\n";
} else {
long long y = x ^ 1;
cout << y << "\n";
}
return 0;
}
Java：[此代码未进行大量数据的测试，仅供参考]
import java.util.Scanner;
// 注意类名必须为 Main，不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
long x = in.nextLong();
if (x == 1) {
System.out.println(-1);
} else {
long y = x ^ 1;
System.out.println(y);
}
in.close();
}
}
Python：[此代码未进行大量数据的测试，仅供参考]
# Python 3
import sys
def main():
data = sys.stdin.read().strip().split()
if not data:
return
x = int(data[0])
if x == 1:
print(-1)
else:
print(x ^ 1)
if __name__ == "__main__":
main()
第二题
题目：音乐队列
小红的播放器里一共有n首歌待放，歌单里第i首歌的长度为ai秒。小红会按顺序播放歌单里的歌，如果当前歌放完了，会自动插放下一首，两首歌曲之间没有缓冲的时间。第i首歌曲的等待时长为a1+…+ai-1秒，第一首歌曲等待时间为0秒。小红想知道，如果她选择k首歌移除播放队列，那么播放队列中剩下的歌曲的等待时长之和最小能达到多少?
输入描述
第一行输入两个整数n(1≤n ≤5000;0≤k≤n)表示歌单里歌曲的数量、需要移除的歌曲数量。
第二行输入n个整数，表示每首歌的长度，其中1<=ai<=10^9。
输出描述
输出一个整数，表示插放队列中剩下的歌曲的等待时长之和的最小值。
样例输入
3 1
1 2 3
样例输出
1
说明：取消最后一首歌
参考题解
1.目标转换： 最小化移除 k 首歌后的总等待时间，等价于最大化移除这 k 首歌所能 减少 的总等待时间。2、计算单次移除收益： 对于原始列表中的每一首歌 a_j，计算如果 只 移除它，会使原始总等待时间减少多少。这个减少量 R_j 等于 a_j 原本的等待时间加上 a_j 对其后面所有歌曲等待时间的贡献（即 a_j 的长度乘以它后面歌曲的数量）。3、贪心选择： 既然要最大化总减少量，并且移除每首歌的“收益” R_j 是基于原始列表计算的，可以独立看待。因此，采用贪心策略：计算所有歌曲的 R_j，然后选择 R_j 值最大的 k 首歌进行移除。4、计算结果：确定要移除的 k 首歌的原始索引。 构建一个只包含剩下 n-k 首歌的新列表（保持它们的原始相对顺序）。 直接计算这个新列表的总等待时间。 核心思想是 贪心，优先移除那些能最大程度降低总等待时间的歌曲。
C++：[此代码未进行大量数据的测试，仅供参考]
#include <bits/stdc++.h>
using namespace std;
struct ReductionInfo {
long long reduction;
int idx; // 1-based index
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<long long> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
// If we remove all songs
if (k == n) {
cout << 0 << "\n";
return 0;
}
// If we remove none, compute original wait
if (k == 0) {
long long totalWait = 0, prefix = 0;
for (int i = 0; i < n; i++) {
totalWait += prefix;
prefix += a[i];
}
cout << totalWait << "\n";
return 0;
}
// Compute prefix sums
vector<long long> prefix(n+1, 0);
for (int i = 0; i < n; i++) {
prefix[i+1] = prefix[i] + a[i];
}
// Build reduction list
vector<ReductionInfo> red;
red.reserve(n);
for (int j = 1; j <= n; j++) {
// R_j = prefix[j-1] + (n-j)*a[j-1]
long long rj = prefix[j-1] + (long long)(n - j) * a[j-1];
red.push_back({rj, j});
}
// Sort by reduction descending, tie by index ascending
sort(red.begin(), red.end(), [](auto &x, auto &y){
if (x.reduction != y.reduction)
return x.reduction > y.reduction;
return x.idx < y.idx;
});
// Mark removed
vector<bool> removed(n+1, false);
for (int i = 0; i < k; i++) {
removed[ red[i].idx ] = true;
}
// Compute final wait on kept songs
long long finalWait = 0, cur = 0;
for (int i = 1; i <= n; i++) {
if (!removed[i]) {
finalWait += cur;
cur += a[i-1];
}
}
cout << finalWait << "\n";
return 0;
}
Java：[此代码未进行大量数据的测试，仅供参考]
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;
public class Main {
// Class to store reduction value and original index
static class ReductionInfo {
long reduction;
int originalIndex; // 1-based index
ReductionInfo(long reduction, int originalIndex) {
this.reduction = reduction;
this.originalIndex = originalIndex;
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int k = scanner.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = scanner.nextInt();
}
if (k == n) {
System.out.println(0); // If all songs are removed, waiting time is 0
scanner.close();
return;
}
if (k == 0) {
// Calculate original waiting time directly if k=0
long totalWait = 0;
long currentPrefixSum = 0;
for (int i = 0; i < n; i++) {
totalWait += currentPrefixSum;
currentPrefixSum += a[i];
}
System.out.println(totalWait);
scanner.close();
return;
}
// Calculate prefix sums
long[] prefixSum = new long[n + 1];
prefixSum[0] = 0;
for (int i = 0; i < n; i++) {
prefixSum[i + 1] = prefixSum[i] + a[i];
}
// Calculate reduction for each song
List<ReductionInfo> reductions = new ArrayList<>();
for (int j = 1; j <= n; j++) {
// R_j = P[j-1] + (n-j) * a[j-1]
long rj = prefixSum[j - 1] + (long)(n - j) * a[j - 1];
reductions.add(new ReductionInfo(rj, j));
}
// Sort reductions in descending order
reductions.sort(new Comparator<ReductionInfo>() {
@Override
public int compare(ReductionInfo r1, ReductionInfo r2) {
// Sort by reduction descending. If reductions are equal, order doesn't matter much,
// but consistent sorting is good (e.g., by index ascending).
int cmp = Long.compare(r2.reduction, r1.reduction); // Descending reduction
if (cmp == 0) {
return Integer.compare(r1.originalIndex, r2.originalIndex); // Ascending index as tie-breaker
}
return cmp;
}
});
// Identify indices to remove
Set<Integer> removedIndices = new HashSet<>();
for (int i = 0; i < k; i++) {
removedIndices.add(reductions.get(i).originalIndex);
}
// Build the new list of songs (kept songs)
List<Int
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
2025打怪升级记录，大厂笔试合集 C++, Java, Python等多种语言做法集合指南
你在犹豫什么
投递美团等公司10个岗位
