A29781. 拼大数
填空题
中等
知识点
题目描述
拼大数
题目描述
如何随机生成一个有n个数的大数呢？一种方法是，找到n个小朋友，每人发一张卡片，卡片一面写着编号（这里假设小朋友们从1到n编号），另一面让他们随便写下一个1位数字。然后让小朋友们把自己的卡片在墙上钉成一排，要求一张挨着一张，按他们的编号升序排列，显示他们自己写的的数字。
但是，让十万个小孩都按指令行动，可太难了。结果是卡片乱七八糟满墙都是，有些甚至显示的不是正确的面。例如，第 23 号小朋友在卡片上写8，我们在墙上应该看到8，但是却看到了23......你的任务就是把这些卡片整理好，得到我们真想要拼成的大数。
输入
输入第一行给出一个正整数 n (≤105)
然后n行，每行按 n1 n2 的格式给出一张卡片两面的数字。
输出
在一行中输出我们真想要拼成的n位大数。如果卡片两面都是1位数，那么就很难说哪个数字是小朋友自己写的，所以解可能是不唯一的。这时候需要输出能得到的最小的数字。
(保证是n位数)
输入样例
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参考答案
#include<iostream>
using namespace std;
/* 思路：
根据小朋友编号来考虑
只有编号小于10的9个小朋友才需要考虑他们真正的编号
大于等于10的那些小朋友根据卡牌两边数字能知道（写的数字只能是1位）
使用深搜找出“个位编号”小朋友的位置，
找出所有可能，取最小
*/
struct node {
int n1;
int n2;
int flag; //用于深搜是否被遍历过
};
int n,cnt=0; //cnt：不确定的数字(1位数)个数
node t[15];
int num[100005]= {0};
int search_ans[15]= {-1}; //搜索的答案临时保存位置，0号位置-1为是否第一次找到
void dfs(int x) { //当前找编号x
if(x>=10 || x>cnt) { //1~9都找到了 找完了
//先判断是否比之前答案小
if(search_ans[0]==-1) { //第一次找到
search_ans[0]=1; //标记不是第一次找到
for(int i=1; i<=cnt; i++) num[i]=search_ans[i];
} else { //非第一次，判断是否更小
for(int i=1; i<=cnt; i++) {
if(search_ans[i]>num[i])
return; //不是更小的
if(search_ans[i]<num[i]) { //更小
for(int j=1; j<=cnt; j++) num[j]=search_ans[j];
return;
}
}
}
return;
}
for(int i=0; i<cnt; i++) { //遍历t数组，找编号x
if(t[i].flag==0) { //还没被遍历过
if(t[i].n1==x || t[i].n2==x) { //n1或n2是编号i
t[i].flag=1; //标记访问
//1是编号哪2就是数字，反之一样
search_ans[x]= (t[i].n1==x) ? t[i].n2:t[i].n1;
dfs(x+1); //搜索下一个
t[i].flag=0; //回溯
}
}
}
}
int main() {
cin>>n; //输入n个小朋友
for(int i=0; i<n; i++) {
int n1,n2;
cin>>n1>>n2;
if(n1>n2) swap(n1,n2); //小的可能是编号，放前面
if(n2>=10) num[n2]=n1; //n2肯定是编号，n1是1位数
else { //两个都是1位数 ,放入t数组
t[cnt].n1=n1;
t[cnt].n2=n2;
t[cnt].flag=0; //用于深搜是否被遍历过
cnt++;
}
}
dfs(1); //深搜
for(int i=1; i<=n; i++) //输出答案
cout<<num[i];
return 0;
}
上一题
下一题