HDU - 稳定排序
发布日期:2021-07-01 00:14:33
浏览次数:2
分类:技术文章
本文共 2295 字,大约阅读时间需要 7 分钟。
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Problem Description
大家都知道,快速排序是不稳定的排序方法。
如果对于数组中出现的任意a[i],a[j](i<j),其中a[i]==a[j],在进行排序以后a[i]一定出现在a[j]之前,则认为该排序是稳定的。 某高校招生办得到一份成绩列表,上面记录了考生名字和考生成绩。并且对其使用了某排序算法按成绩进行递减排序。现在请你判断一下该排序算法是否正确,如果正确的话,则判断该排序算法是否为稳定的。Input
本题目包含多组输入,请处理到文件结束。
对于每组数据,第一行有一个正整数N(0<N<300),代表成绩列表中的考生数目。 接下来有N行,每一行有一个字符串代表考生名字(长度不超过50,仅包含'a'~'z'),和一个整数代表考生分数(小于500)。其中名字和成绩用一个空格隔开。 再接下来又有N行,是上述列表经过某排序算法以后生成的一个序列。格式同上。Output
对于每组数据,如果算法是正确并且稳定的,就在一行里面输出"Right"。如果算法是正确的但不是稳定的,就在一行里面输出"Not Stable",并且在下面输出正确稳定排序的列表,格式同输入。如果该算法是错误的,就在一行里面输出"Error",并且在下面输出正确稳定排序的列表,格式同输入。
注意,本题目不考虑该排序算法是错误的,但结果是正确的这样的意外情况。Sample Input
3
aa 10 bb 10 cc 20 cc 20 bb 10 aa 10 3 aa 10 bb 10 cc 20 cc 20 aa 10 bb 10 3 aa 10 bb 10 cc 20 aa 10 bb 10 cc 20
Sample Output
Not Stable
cc 20 aa 10 bb 10 Right Error cc 20 aa 10 bb 10
Problem solving report:
Description: 按照要求判断所给排序是否为稳定排序。
Problem solving: 先把成绩排一下序(如果成绩相同,不用交换),然后字符串跟着与成绩相同的顺
序排序,然后和所给排序进行比较,看看对不对得上。#includeint main(){ int s[310], p[310], i, j, t, n; char a[310][110], b[310][110], c[110]; while (~scanf("%d%*c", &n)) { for (i = 0; i < n; i++) { gets(a[i]); sscanf(a[i], "%*s%d", &s[i]); } for (i = 0; i < n; i++) { gets(b[i]); sscanf(b[i], "%*s%d", &p[i]); } for (i = 0; i < n - 1; i++) { for (j = 0; j < n - i - 1; j++) { if (s[j] < s[j + 1]) { t = s[j]; s[j] = s[j + 1]; s[j + 1] = t; strcpy(c, a[j]); strcpy(a[j], a[j + 1]); strcpy(a[j + 1], c); } } } for (i = 0; i < n; i++) if (strcmp(a[i], b[i])) break; for (j = 0; j < n; j++) if (s[j] != p[j]) break; if (i == n && j == n) printf("Right\n"); else if (j == n) { printf("Not Stable\n"); for (j = 0; j < n; j++) printf("%s\n", a[j]); } else { printf("Error\n"); for (j = 0; j < n; j++) printf("%s\n", a[j]); } } return 0;}
转载地址:https://lzyws739307453.blog.csdn.net/article/details/83245216 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
第一次来,支持一个
[***.219.124.196]2024年04月27日 09时09分25秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
IP地址分类
2019-05-01
PHP清洗过滤器Sanitize filters
2019-05-01
PHP回调过滤器及回调函数写法
2019-05-01
PHP命名空间简介
2019-05-01
Myeclipse安装testng插件(插件式安装)
2019-05-01
PHP动态访问元素时命名空间的使用
2019-05-01
PHP命名空间导入、别名
2019-05-01
PHP命名空间解析规则
2019-05-01
PHP函数处理函数
2019-05-01
FireFox标签页在新标签页打开
2019-05-01
Tcl列表元素查找命令lsearch
2019-05-01
Tcl列表命令之lmap、lrange、lrepeat、lreverse
2019-05-01
PHP调试器Xdebug安装
2019-05-01
PHP运行报错:由于找不到 MSVCR110.dll,无法继续执行代码。的解决办法
2019-05-01
WampServer多PHP版本支持
2019-05-01
Tcl列表命令之concat、join
2019-05-01
Tcl数据结构之数组
2019-05-01
Tcl数组命令之array
2019-05-01
Tcl数据结构之字典
2019-05-01
Windows安装Composer
2019-05-01