编程团体赛

目录

1047:编程团体赛

输入格式：

输出格式：

输入样例：

输出样例：

思路:

代码:

时间复杂度:

总结:

题目链接:

---

1047:编程团体赛

编程团体赛的规则为：每个参赛队由若干队员组成；所有队员独立比赛；参赛队的成绩为所有队员的成绩和；成绩最高的队获胜。

现给定所有队员的比赛成绩，请你编写程序找出冠军队。

输入格式：

输入第一行给出一个正整数 N（≤104），即所有参赛队员总数。随后 N 行，每行给出一位队员的成绩，格式为：队伍编号-队员编号 成绩，其中队伍编号为 1 到 1000 的正整数，队员编号为 1 到 10 的正整数，成绩为 0 到 100 的整数。

输出格式：

在一行中输出冠军队的编号和总成绩，其间以一个空格分隔。注意：题目保证冠军队是唯一的。

输入样例：

6
3-10 99
11-5 87
102-1 0
102-3 100
11-9 89
3-2 61

输出样例：

11 176

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

思路:

    我们看到这个题目,是输出总分最高的队伍,那肯定需要排序,排序之后为了保证队伍名称不错乱
    我们可以定义一个结构来解决.
      一个结构,需要:
        name:是这个队伍的编号
        x:这个队伍里面队员的编号
        s:这个队伍目前的总成绩
      这个结构我们可以定义一个数组a,大小就是1001,毕竟题目中说明了队伍编号最多是1000.
    输入之后,就可以开始结构体排序了.
    如果用STL库默认的sort函数来排序,是不行的,因为我们这个结构在库里面没有定义.
    那我们怎么办呢?
    我们可以自己来定义一下这个sort排序的排序规则.
    写一个cmp函数,参数是两个队伍结构,因为我们是找冠军,就可以定义他们的s(成绩)来比谁大.
    排序过后,因为是从大到小排序,下标为0的地方就是成绩最大的队伍.
    然后将其输出. 

代码:

//1047编程团体赛:
//正解: 
#include
using namespace std;
struct dw{ //定义一个结构 
	int name; //队伍编号 
	int x; //学员成绩 
	int s; //队伍总成绩 
	dw(){ //结构函数初始化 
		x=0; //都初始化为0 
		s=0;
	}
}a[1001];//定义队伍数组 
bool cmp(dw a,dw b){ //自定义排序方式 
	return a.s>b.s; //由两个队伍的总成绩大小来比 
}
int main(){
	int n,i=0;
	cin>>n;
	int b[n];
	while(n--){ //输入 
		int y;
		char c;
		cin>>b[i]; //队伍的编号 
		a[b[i]].name=b[i]; //赋值 
		cin>>c; //输入里面有一个'-' 
		cin>>a[b[i]].x>>y;//输入队员的编号和成绩 
		a[b[i]].s+=y;//加到总成绩里面 
		i++;
	}
	sort(a,a+1001,cmp);//排序 
	cout<0].name<<" "<0].s<//输出冠军 
	return 0;
} 

时间复杂度:

STL库sort函数是冒泡排序,原本复杂度是O(N^2); 
在这里,a的长度最大是10^3=1001
那么真正时间复杂度就是O(10^3^2)=O(10^6); 
虽然这个复杂度以及可以AC本题了,但是我们还可以优化:
    可以应用STL库中的qsort函数 
    该函数内部写的是快速排序的代码
    一般来说,快速排序是O(N)的复杂度
    最快就可以优化到O(10^3);
    快了不少,不过前面这个冒泡排序就已经不超时了,这个优化算是多此一举. 

总结:

  这道题考的是对结构的应用以及结构体的排序.

题目链接:

PTA | 程序设计类实验辅助教学平台千名教师建设，万道高质量题目，百万用户拼题的程序设计实验辅助教学平台https://pintia.cn/problem-sets/994805260223102976/exam/problems/994805277163896832