首页 › 题库 › C/C++编程考级 › C/C++编程三级 › 简答题
简答题 偏难
#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 &lt;iostream&gt; #include &lt;vector&gt; #include &lt;queue&gt; using namespace std; int main() {     int n;     cin &gt;&gt; n;     vector&lt;priority_queue&lt;pair&lt;int, int&gt;, vector&lt;pair&lt;int, int&gt;&gt;, greater&lt;pair&lt;int, int&gt;&gt;&gt;&gt; pq(n + 1);     vector&lt;pair&lt;int, int&gt;&gt; cards(n);     for (int i = 0; i &lt; n; ++i) {         int a, b;         cin &gt;&gt; a &gt;&gt; b;         cards[i].first = a;         cards[i].second = b;         // Check if a is a valid id and b is a valid digit         if (a &gt;= 1 &amp;&amp; a &lt;= n &amp;&amp; b &gt;= 0 &amp;&amp; b &lt;= 9) {             pq[a].emplace(b, i);         }         // Check if b is a valid id and a is a valid digit         if (b &gt;= 1 &amp;&amp; b &lt;= n &amp;&amp; a &gt;= 0 &amp;&amp; a &lt;= 9) {             pq[b].emplace(a, i);         }     }     vector&lt;bool&gt; used(n, false);     vector&lt;int&gt; result(n + 1, -1);     for (int i = 1; i &lt;= 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 &lt;&lt; "No solution" &lt;&lt; endl;             return 0;         }     }</pre>
这道题暂未补解析。