E - 稳定排序(结构体)
2024-09-07 02:30:50
大家都知道,快速排序是不稳定的排序方法。
如果对于数组中出现的任意a[i],a[j](i<j),其中a[i]==a[j],在进行排序以后a[i]一定出现在a[j]之前,则认为该排序是稳定的。
如果对于数组中出现的任意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
题解:先按照题目要求,写出稳定排序,(注意这里是如果分数相同则按照先出现的排在前面,而不是按照姓名的字典序进行排列),然后再进行比较即可。
AC代码
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std; struct nood
{
char name[];
int score;
int data;
} student[], solution[]; bool cmp(nood a, nood b)
{
if(a.score == b.score)
{
return a.data < b.data;
}
else
{
return a.score > b.score;
}
} int main()
{
int n;
bool flag1, flag2;
while(~scanf("%d", &n))
{
flag1 = flag2 = true;
for(int i = ; i < n; i++)
{
scanf("%s %d", student[i].name, &student[i].score);
student[i].data = i;
}
for(int i = ; i < n; i++)
{
scanf("%s %d", solution[i].name, &solution[i].score);
}
sort(student, student+n, cmp);
for(int i = ; i < n; i++)
{
if(solution[i].score != student[i].score)
{
flag1 = false;
break;
}
}
for(int i = ; i < n; i++)
{
int name_cmp = strcmp(solution[i].name, student[i].name);
if(name_cmp)
{
flag2 = false;
break;
}
}
if(flag1 && flag2)
printf("Right\n");
else if(flag1 && !flag2)
{
printf("Not Stable\n");
for(int i = ; i < n; i++)
printf("%s %d\n", student[i].name, student[i].score);
}
else if(!flag1 && !flag2)
{
printf("Error\n");
for(int i = ; i < n; i++)
printf("%s %d\n", student[i].name, student[i].score);
}
} return ;
}
最新文章
- JS获取当前时间戳的方法
- 使用EntityFramework6连接MySql数据库(db first方式)
- linux设备驱动归纳总结(四):1.进程管理的相关概念【转】
- JavaScript学习记录总结(七)——dom对象应用之用户简单管理
- jenkins-slave的搭建和使用
- 【CSS3】---嵌入字体@font-face
- COJ WZJ的数据结构(负十八)splay_tree的天堂
- 201521123075 《Java程序设计》第11周学习总结
- python 全栈开发,Day91(Vue实例的生命周期,组件间通信之中央事件总线bus,Vue Router,vue-cli 工具)
- Mysql索引引起的死锁
- 『翻译』Access USB Devices on the Web
- Haskell语言学习笔记(80)req
- android - 调用系统分享功能分享图片
- spring boot 整合案例
- 通过sizeof获得数组长度的方法
- 【slenium专题】Webdriver同步设置
- 微软正式发布Windows 1.0 回顾历代Windows版本界面
- Html生成控件
- C#启动外部程序以及等待外部程序关闭的几种方法
- c++ 中 毫秒级时间获取