首页 > 代码库 > 1028. List Sorting (25)

1028. List Sorting (25)

这道题目主要是排序,刚开始简单写了一个代码,发现最后一个测试数据。发现超时了,sort排序用的是快排。快排平均是O(NlogN),最坏是O(N*N)。输入数据是10^5级的,最坏的情况会超过10^10,会超时。所以刚开始想用其他排序方法

sort()---排序

stable_sort---稳定排序

heap_sort()--堆排序(make_heap(a,a+n,cmp1)),heap_sort(a,a+n,cmp1);

最后网上找了一下答案,发现说是输入的原因,所以换成scanf来输入,从char a[20];string str(a);从char a[22]-->string;

发现还是超时,然后把输出也换成printf来输出。最后通过了,cin,cout的效率是比较低,以后还是尽量用scanf,printf吧

// 1028.cpp : 定义控制台应用程序的入口点。//#include<string>#include<iostream>#include<algorithm>using namespace std;struct Student{    string id;    string name;    int score;}stu[100010];bool cmp1(const Student & a,const Student &b){    if(a.id<b.id)        return true;    return false;}bool cmp2(const Student & a,const Student &b){    if(a.name<b.name)        return true;    else if(a.name==b.name)    {        if(a.id<b.id)            return true;    }    return false;}bool cmp3(const Student & a,const Student &b){    if(a.score<b.score)        return true;    else if(a.score==b.score)        {        if(a.id<b.id)           return true;    }    return false;}int main(){    int n,c;    while(cin>>n>>c)    {        char id[12];        char name[12];        for(int i=0;i<n;i++)        {            //cin>>stu[i].id>>stu[i].name>>stu[i].score;            scanf("%s%s%d",id,name,&stu[i].score);             stu[i].id=string(id);            stu[i].name=string(name);        }                switch(c)        {        case 1:            make_heap(stu,stu+n,cmp1);            sort_heap(stu,stu+n,cmp1);            break;        case 2:            make_heap(stu,stu+n,cmp2);            sort_heap(stu,stu+n,cmp2);            break;        case 3:            make_heap(stu,stu+n,cmp3);            sort_heap(stu,stu+n,cmp3);            break;        }        for(int i=0;i<n;i++)        {            //cout<<stu[i].id<<" "<<stu[i].name<<" "<<stu[i].score<<endl;            printf("%s %s %d\n",stu[i].id.c_str(),stu[i].name.c_str(),stu[i].score);        }    }    return 0;}

 

1028. List Sorting (25)