首页 > 代码库 > 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)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。