拼多多笔试 拼多多笔试题 0409
笔试时间：2025年04月09日
历史笔试传送门：
第一题
题目：披萨餐厅
Gerry的店里有n个顾客使用兑换券兑换m个糖果。单张兑换券可以兑换k个糖果。 单次兑换所需的兑换券数y与糖果数x有如下关系，类似四舍五入：y=⌈x/k⌉,(if x mod k >= ⌈k/2⌉)y=⌊x/k⌋,(if x mod k < ⌈k/2⌉)*注：⌈⌉代表向上取整，⌊⌋代表向下取整，mod代表取模。 Gerry有如下要求：每个顾客最多交易1次m个糖果需要全部兑换完Gerry想知道要兑换完所有的糖果，至少需要多少张兑换券，请帮忙计算一下。
输入描述
第一行个数字T（1≤T≤1000）
接下来T行，每行三个数字：
n,m,k;(1 ≤n≤10^9,1 ≤m ≤10^18,2≤k≤10^9)
输出描述
输出T行，每行一个数字，代表最少需要用的兑换券个数
样例输入
3
3 300 100
36 96 6
73 176 22
样例输出
2
4
0
参考题解
贪心，为了不让优惠券亏掉，先让n-1个人都用一张券换最多的糖果，剩下的糖果都让最后一个人来换，这样消耗的优惠券数量最少。
C++：[此代码未进行大量数据的测试，仅供参考]
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
long long n, m, k;
cin >> n >> m >> k;
long long res = 0;
long long t = (k + 1) / 2 - 1;
m -= t * (n - 1);
if (m <= 0) {
cout << 0 << "\n";
continue;
}
long long yu = m % k;
res += m / k;
if (yu > t) {
res++;
}
cout << res << "\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));
int T = Integer.parseInt(br.readLine());
while (T-- > 0) {
StringTokenizer st = new StringTokenizer(br.readLine());
long n = Long.parseLong(st.nextToken());
long m = Long.parseLong(st.nextToken());
long k = Long.parseLong(st.nextToken());
long res = 0;
long t = (k + 1) / 2 - 1;
m -= t * (n - 1);
if (m <= 0) {
System.out.println(0);
continue;
}
long yu = m % k;
res += m / k;
if (yu > t) {
res++;
}
System.out.println(res);
}
}
}
Python：[此代码未进行大量数据的测试，仅供参考]
def solve(): n, m, k = map(int, input().split()) res = 0 t = (k + 1) // 2 - 1 m -= t * (n - 1) if m <= 0: print(0) return yu = m % k res += m // k if yu > t: res += 1 print(res) T = int(input()) for _ in range(T): solve()
第二题
题目：操作数列
多多有两个仅由正整数构成的数列 s1 和 s2，多多可以对 s1进行任意次操作,每次操作可以置换 s1中任意两个数字的位置.多多想让数列 s1 构成的数字尽可能大,但是不能比数列 s2构成的数字大.请问再经过任意次操作后,满足上述条件的数列 s1构成的数字是多少？
输入描述
第一行,包含一个正整数T(1 ≤T≤10)代表测试数据的组数
对于每组测试数据,分别有三行:第一行,有两个正整数 n(1 <n<10^5),m(1 ≤m ≤ 10^5),分别表示数列 s1 和 s2 的长度
第二行,有一行仅由正整数组成的的长度为 n 数列 s1.
第三行,有一行仅由正整数组成的的长度为 m 数列 s2
输出描述
对于每组数据,输出数列 s1在经过任意次置换操作后,得到的满足条件的最大值数字.如果不存在这样的数字,则输出 -1.
样例输入
3
5 5
12748
34514
5 5
18715
51721
5 5
69568
52137
样例输出
28741
51718
-1
参考题解
位数差异判断当s1位数 < s2位数：直接降序排列s1即可（位数少必然更小）当s1位数 > s2位数：必然无法满足条件，直接返回-1等长时的构造策略从高位到低位遍历，每个位置尽可能选最大的可用数字需满足两种情况之一： a. 当前位数字严格小于s2对应位，后续位可以填最大可用数 b. 当前位数字等于s2对应位，继续按相同规则处理下一位若无法满足上述条件则需要回溯关键难点需要处理数字重复使用的情况（用计数器统计剩余可用数字）通过栈模拟回溯过程，当然递归应该也可以，python选手注意栈空间。维护"是否已存在某位比s2小"的状态，决定后续位的自由度。
C++：[此代码未进行大量数据的测试，仅供参考]
#include <bits/stdc++.h>
using namespace std;
struct State {
int index;
bool iless;
State(int i, bool l) : index(i), iless(l) {}
};
void solve() {
int N, M;
cin >> N >> M;
string s1, s2;
cin >> s1 >> s2;
// 情况1：s1 位数 < s2 位数，直接输出 s1 的最大排列
if (N < M) {
vector<int> cnt(10, 0);
for (char c : s1) {
cnt[c - '0']++;
}
// 从 9 到 0 降序拼接
for (int d = 9; d >= 0; d--) {
for (int k = 0; k < cnt[d]; k++) {
cout << char('0' + d);
}
}
cout << "\n";
return;
}
// 情况2：s1 位数 > s2 位数，直接返回 -1
if (N > M) {
cout << "-1\n";
return;
}
// 情况3：等长时，需要在不超过 s2 的前提下，用 s1 的数字拼最大数
vector<int> cnt(10, 0);
for (char c : s1) {
cnt[c - '0']++;
}
vector<char> ans(N, '\0'); // 最终答案字符数组，初始都为 '\0'
// 栈模拟回溯：存放 (当前处理位 index, 是否已小于 s2 的标志 iless)
vector<State> stk;
stk.reserve(N + 5);
stk.emplace_back(0, false);
while (!stk.empty()) {
State &top = stk.back();
int index = top.index;
bool iless = top.iless;
// 如果 index == N，已经构造出一个合法解
if (index == N) {
for (char c : ans) {
cout << c;
}
cout << "\n";
return;
}
// 计算当前位可尝试的最大数字 sdval
int sdval;
if (ans[index] == '\0') {
// 首次处理该位
int limit = iless ? 9 : (s2[index] - '0');
sdval = limit;
} else {
// 回溯时：先把之前使用的数字归还，再尝试更小的
int prevDigit = ans[index] - '0';
cnt[prevDigit]++;
ans[index] = '\0';
sdval = prevDigit - 1;
}
bool foundNext = false;
// 从 sdval 向下尝试可用数字
for (int d = sdval; d >= 0; d--) {
if (cnt[d] > 0) {
ans[index] = char('0' + d);
cnt[d]--;
bool nextIless = iless || (d < (s2[index] - '0'));
stk.emplace_back(index + 1, nextIless);
foundNext = true;
break;
}
}
if (!foundNext) {
// 本位所有数字都不行，回溯
stk.pop_back();
}
}
// 尝试完所有可能性，仍未构造出解
cout << "-1\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
solve();
}
return 0;
}
Java：[此代码未进行大量数据的测试，仅供参考]
import java.io.*;
import java.util.*;
public class Main {
static void solve(BufferedReader br, StringBuilder sb) throws IOException {
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
String s1 = br.readLine().trim();
String s2 = br.readLine().trim();
// 情况1：s1 位数 < s2 位数，直接输出 s1 的最大排列
if (N < M) {
int[] cnt
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
2025打怪升级记录，大厂笔试合集 C++, Java, Python等多种语言做法集合指南
