题目1339:ACM
- 题目描述:
-
今年的ACM世界总决赛快要开始了,需要有一个排名算法来对每支队伍进行现场排名。ACM组委会把这个任务交给了你,相信你一定能很好地完成。
排名规则如下:通过题的数目多的队伍排名靠前,如果有多支队伍过的题的数目相同,则罚时少的队伍排名靠前。
- 输入:
-
输入的第一行包括一个整数N(1<=N<=100),代表参加比赛的队伍的个数。
接下来的N行每行包括一个字符串和两个整数num,punish,它们之间用空格隔开。其中,第一个字符串代表参赛的队伍名称(字符串的长度1<=len<=101),num代表这个学校过了的题目个数(1<=num<=11),punish代表这个学校的罚时(1<=punish<=1000)。
- 输出:
-
请按题目描述的规则对所有队伍进行排序,并按照从高到低的顺序对队伍的名称进行输出。当然可能存在多支队伍,不仅通过题目数量相同,而且罚时相同。虽然这些队伍最后排名是相同的,但是你输出时需要按照队伍名称的字典序进行输出,比如,队伍aa和队伍ba,你需要先输出aa,然后输出ba,因为aa的字典序比ba的靠前。
- 样例输入:
-
4 RealPlayers 3 100 Potatoes 5 30 blue_sky 7 800 3D_magic_cube 5 50
- 样例输出:
-
blue_sky Potatoes 3D_magic_cube RealPlayers
算法分析
程序的关键在于排序算法中比较函数的书写,此题和 1346:会员积分排序
是同一类型的题目。
是同一类型的题目。
先判断 通过题目数相同,罚时时间相同情况, 按照队伍名称的字典序比较
再判断 通过题目数相同情况,按照罚时时间比较
后判断 按照通过题目数比较
这样的写法,代码比较简洁
源程序
//============================================================================ // Name : judo1339.cpp // Author : wdy // Version : // Copyright : Your copyright notice // Description : Hello World in C++, Ansi-style //============================================================================ //similar to 1346 1339 1347 #include <iostream> #include <string> #include <vector> #include <algorithm> using namespace std; struct Team{ public: std::string name; int num; int punish; public: Team(string name_,int num_,int punish_):name(name_),num(num_),punish(punish_){}; }; bool preThan(const Team& ta,const Team& tb){ if(ta.num == tb.num && ta.punish==tb.punish){ return ta.name<tb.name; }else if(ta.num == tb.num) return ta.punish < tb.punish; else return ta.num>tb.num; } void sortTeam(int n){ std::vector<Team> ts; std::string name; int num; int punish; for(int i = 0;i<n;i++){ std::cin>>name>>num>>punish; ts.push_back(Team(name,num,punish)); } std::sort(ts.begin(),ts.end(),preThan); for(int i = 0;i<n;i++){ std::cout<<ts[i].name<<std::endl; } } void judo(){ int n; while(std::cin>>n){ sortTeam(n); } } int main() { judo(); //cout << "!!!Hello World!!!" << endl; // prints !!!Hello World!!! return 0; } /************************************************************** Problem: 1339 User: KES Language: C++ Result: Accepted Time:70 ms Memory:1524 kb ****************************************************************/