1.14 拼多多2024校招笔试真题

1.14.1 多多的数字组合

【题目描述】

给定一个整数N，求一个最小值，要求：

1)各个数位的数字之和等于N

2)各个数位的数字各不相同

【解题思路】

由于每个数字0～9只能用一次，且要求为最小值，所以优先保证数字的位数最少。

同时对于相同的位数，由于和均为N的情况下，位数越小数字应该越大，因此可以使用贪心的方法。

从低位到高位，从9～0倒序依次枚举可以使用的数字，直到满足和等于N，否则无解。

考虑点： 数位，贪心

【参考代码】

#include<bits/stdc++.h>

using namespace std;

int main() {

int n;

while (cin >> n) {

int ans = 0, p = 1;

for (int i = 9; i > 0; i--) {

if (n >= i) {

n -= i;

ans += p * i;

p *= 10;

}

}

if (n > 0) {

cout << -1 << endl;

} else {

cout << ans << endl;

}

}

return 0;

}

1.14.2 多多的字符变换

【题目描述】

给定两个长度相同的字符串，支持两种变换方式：

1)交换任意两个相邻的字符，代价为0。

2)将任意一个字符a修改成字符b，代价为 |a - b|（绝对值）。

要求将两个字符串变成一样的字符串最小需要的代价之和。

【解题思路】

从两种变换方式的组合来看，由于方式(1)的代价为0，即可以无代价多次重复使用。

于是可以通过排序的方式，先将两个字符串变成有序字符串。

在排序后两个字符串对应位置的字符距离分别为最小值，且任意交互两组位置后的差值会大于等于原差值，因此排序后的差值即为最小值。

考虑点：字符串，比较，贪心

【参考代码】

#include <bits/stdc++.h>

using namespace std;

int main() {

int N;

string X, Y;

while (cin >> N) {

cin >> X >> Y;

sort(X.begin(), X.end());

sort(Y.begin(), Y.end());

int ans = 0;

for (int i = 0; i < N; i++) {

ans += abs(X[i] - Y[i]);

}

cout << ans << endl;

}

return 0;

}

1.14.3 多多的骰子组合

【题目描述】

给出N个骰子（N≤1,000）, 要求将这个骰子进行分类

两个骰子属于同类的定义是：

将其中一个骰子通过若干次上下、左右或前后翻转后，其与另一个骰子对应的6面数字均相等

【解题思路】

两两枚举每个骰子是否同类

因为骰子的变换方向只有3个：上下、左右和前后，并且每个方向翻转4次后会回归原本的状态

即最多进行4*4*4=64次旋转即可遍历到所有状态

判断同类后，进行归类的方法则可以自由选择：

• 选择其中一个骰子作为代表
• 最小表示法，以同类骰子最小的编号作为代表
• 并查集
• 等等

时间复杂度: O(N^2)

优化一：

实际上由于骰子的同构变换只有24种，6面骰子最多的状态为6!=720

于是本质不同