小孩的游戏（数据结构作业）

107 阅读 0 评论 71 点赞

我是靠谱客的博主健忘白开水，这篇文章主要介绍小孩的游戏（数据结构作业），现在分享给大家，希望可以做个参考。

算法与数据结构实验题小孩的游戏

★实验任务

一群孩子在玩游戏，游戏规则是这样子，给了一些卡片，上面有数字，现在要把卡片按照某一种序列排好，让这些数字重新链接组合成一个大数，求最大数是什么。

★数据输入

第一行一个整数 N

接下来 N行，每行一个整数 ai,为第 i 张卡片上数值。(0<=ai<=100)

★数据输出

输出重新组合好大数。

输入示例

输出示例

999923

50%数据 1<= N<=50000

100%数据 1<=N<=100000

典型多关键字排序，采取高位优先排序，这是没有优化的算法复杂度 $o(k*n)$ 。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <cstdio>
#include <vector>
using namespace std;
int getH(int x)
{
if (x>=0 && x<10)
return x;
else if ( x>9 &&x<100)
return x/10;
else
return 1;
}
int getL(int x)
{
if (x>=0 && x<10)
return x;
else if ( x>9 &&x<=100)
return x%10;
}
int main()
{
int n;
int a[100006];
vector <int> bucket[10];//大桶
vector <int> b[10];
//小桶
scanf ("%d",&n);
for (int i=1;i<=n;i++)
{
scanf ("%d",&a[i]);//把元素放入大桶（最按高位分配）
bucket[getH(a[i])].push_back(a[i]);
}
vector <int> :: iterator it;
for (int i=0;i<=9;i++)
{
//每个大桶在进行分配，按照个位分配 。
for (it=bucket[i].begin();it!=bucket[i].end();it++)
{
if (i==1&&*it==10)//10 和 100 特殊处理 10一定比100更优先 。
b[0].insert(b[0].begin(),10);
else
b[getL(*it)].push_back(*it);
}
bucket[i].clear();
//大桶清空，把小桶中已排序好的序列倒入大桶 。
for (int j=9;j>=0;j--)
{
for (it=b[j].begin();it!=b[j].end();it++)
bucket[i].push_back(*it);
b[j].clear();
}
}
//按照从小到大一次输出
for (int i=9;i>=0;i--)
{
for (it=bucket[i].begin();it!=bucket[i].end();it++)
{
printf ("%d",*it);
}
}
printf ("n");
return 0;
}