简答题
偏难
#7537
拼大数 如何随机生成一个有 n 位数的大数呢?一种方法是,找到 n 个小朋友,每人发一张卡片,卡片一面写着编号(这里假设小朋友们从 1 到 n 编号),另一面让…
拼大数
如何随机生成一个有 n 位数的大数呢?一种方法是,找到 n 个小朋友,每人发一张卡片,卡片一面写着编号(这里假设小朋友们从 1 到 n 编号),另一面让他们随便写下一个 1 位数字。然后让小朋友们把自己的卡片在墙上钉成一排,要求一张挨着一张,按他们的编号升序排列,显示他们自己写的数字。
但是,让十万个孩子都按指令行动,可太难了。结果是卡片乱七八糟满墙都是,有些甚至显示的不是正确的面。例如第 23 号小朋友在卡片上写了 8,我们应该在墙上看到 8,但是却看到了 23…… 你的任务就是把这些卡片整理好,得到我们真想要拼成的大数。
时间限制:6000
内存限制:65536
输入
输入第一行给出一个正个整数 n (≤ 105),随后 n 行,每行按 n1 n2的格式给出一张卡片两面的数字。
输出
在一行中输出我们真想要拼成的 n 位大数。 如果卡片两面都是 1 位数,那么就很难说哪个数字是编号,哪个数字是小朋友自己写的,所以解可能是不唯一的。这时候需要输出能得到的最小的数字。
样例输入
12 7 11 8 9 3 1 2 12 4 6 10 0 5 1 2 5 6 8 1 4 7 2 9 3
样例输出
359114268072
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
int n;
cin >> n;
vector<priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>> pq(n + 1);
vector<pair<int, int>> cards(n);
for (int i = 0; i < n; ++i) {
int a, b;
cin >> a >> b;
cards[i].first = a;
cards[i].second = b;
// Check if a is a valid id and b is a valid digit
if (a >= 1 && a <= n && b >= 0 && b <= 9) {
pq[a].emplace(b, i);
}
// Check if b is a valid id and a is a valid digit
if (b >= 1 && b <= n && a >= 0 && a <= 9) {
pq[b].emplace(a, i);
}
}
vector<bool> used(n, false);
vector<int> result(n + 1, -1);
for (int i = 1; i <= n; ++i) {
while (!pq[i].empty()) {
auto [d, idx] = pq[i].top();
pq[i].pop();
if (!used[idx]) {
used[idx] = true;
result[i] = d;
break;
}
}
if (result[i] == -1) {
cout << "No solution" << endl;
return 0;
}
}</pre>
这道题暂未补解析。