hdoj 1872 稳定排序

浏览数：21 / 时间：2015年06月08日

稳定排序

Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4042 Accepted Submission(s): 1581

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

aa 10

bb 10

cc 20

bb 10

aa 10

bb 10

cc 20

aa 10

bb 10

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

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct record  //记录排序前输入的数据 
{
	char name[50];
	int fen;
	int time; 
}s[310];
struct line//记录题目所给的排序后的输入 
{
	char namep[50];
	int fenp;
}sp[310];
bool cmp(record a,record b)
{
     if(a.fen!=b.fen)
     return a.fen>b.fen;
     else
     return a.time<b.time;//数据前后出现的时间早晚 
}
int main()
{
	int n,m,j,i,sum,t,f;
	while(scanf("%d",&n)!=EOF)
	{
		for(i=0;i<n;i++)
		{
			s[i].time=i;
		    scanf("%s%d",s[i].name,&s[i].fen);	
		}
		sort(s,s+n,cmp);
		t=0;f=0;
	    for(i=0;i<n;i++)
	    {
	    	scanf("%s%d",sp[i].namep,&sp[i].fenp);
	        if(strcmp(s[i].name,sp[i].namep)!=0)   //判断两字符串是否相等 
	        t++;
	        if(s[i].fen!=sp[i].fenp)//判断自己的排序与题目中所给排序是否相同 
	        f++;
	    }
	    if(t==0&&f==0)
	    printf("Right\n");
	    if(t!=0&&f==0)
	    {
	    	printf("Not Stable\n");
	    	for(i=0;i<n;i++)
	    	{
	    		printf("%s %d\n",s[i].name,s[i].fen);
	    	}
	    }
	    if(f!=0)
	    {
	    	printf("Error\n");
	    	for(i=0;i<n;i++)
	    	{
	    		printf("%s %d\n",s[i].name,s[i].fen);
	    	}
	    }    
	}
	return 0;
}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

hdoj 1872 稳定排序