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

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

★实验任务

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

★数据输入

第一行一个整数 N

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

★数据输出

输出重新组合好大数。

50%数据 1<= N<=50000

100%数据 1<=N<=100000

典型多关键字排序，采取高位优先排序，这是没有优化的算法 复杂度  。

#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;
} 

最后

以上就是健忘白开水为你收集整理的小孩的游戏 （数据结构作业）的全部内容，希望文章能够帮你解决小孩的游戏 （数据结构作业）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。