挖掘机技术哪家强编程题-编程练习题(100)

问题：

9.	【问题描述】为了用事实说明挖掘机技术到底哪家强，组织一场挖掘机技能大赛。现请你根据比赛结果统计出技术最强的那个学校。【输入形式】输入在第1行给出不超过 $10^{5}$ 的正整数N，即参赛人数。随后N行，每行给出一位参赛者的信息和成绩，包括其所代表的学校的编号、及其比赛成绩（百分制），中间以空格分隔。【输出形式】在一行中给出总得分最高的学校的编号、及其总分，中间以空格分隔。题目保证答案唯一，没有并列。【样例输入】 6 3 65 2 80 1 100 2 70 3 40 3 0 【样例输出】 2 150 【问题说明】建议练习使用STL中的map

分析：

方法1：可以使用数组下标表示学校编号，对应下标存入总分。这种做法存在一个问题，我们并不知道学校的编号是如何编排的，我们只能申请一个100000大小的数组（假设每个人都来自不同学校），会浪费大量的空间，所以最好使用STL中的map容器。

方法2：使用map和数组方法差不多，使用map的key表示学校编号，value表示总分，每次查找map中是否有对应的学校编号，有的话就将当前值和map的value相加再存入map的value中。然后再迭代遍历map找到最大的key输出学校编号和总分。

C++代码（数组实现）：

#include <iostream>
#include <map>

using namespace std;

int main()
{
    int N;   //参赛人数
    int athlete[100000] = {0};
    int sub; //数组下标
    int temp;

    cin >> N;
    for(int i=0; i<N; i++)
    {
        cin >> sub;
        cin >> temp;
        athlete[sub] += temp;
    }
    sub = 1;
    for(int j=2; j<1000000; j++)
    {
        if(athlete[sub] < athlete[j])
        {
            sub = j;
        }
    }
    cout << sub << ' ' << athlete[sub] <<endl;
    return 0;
}

C++STL代码（map实现）：

#include <iostream>
#include <map>

using namespace std;

int main()
{
    int N;                       //参赛人数
    map<int,int> mapAthlete;     //存放参赛学校编号及总分
    map<int,int>::iterator iter; //迭代器
    int key;          //键值
    int temp;         //中间变量
    int maxScor = 0;  //总分最大

    cin >> N;
    for(int i=0; i<N; i++)
    {
        cin >> key;
        cin >> temp;
        iter = mapAthlete.find(key);  //在map中查找key学校是否存在
        if(iter != mapAthlete.end())  //如果存在的话就只将分数加进总分，不存在就新加入一个
        {
            iter->second = iter->second + temp;
        }else{
            mapAthlete[key] = temp;
        }
    }

    for(iter = mapAthlete.begin() ; iter != mapAthlete.end() ; iter++)  //找到总分最大的学校编号及分数
    {
        if(iter->second > maxScor)
        {
            maxScor = iter->second;
            key = iter->first;
        }
    }
    cout << key << ' ' <<maxScor;
    return 0;
}

总结：

这道题使用数组也可以，但是使用map容器的好处就是节省空间，而且时间复杂度也会小很多，如果使用数组，不光得申请 $10^{5}$ 大小的数组，还得循环 $10^{5}$ 次才能找到最大的总分。再就是学校编号不确定，如果学校编号使用类似201810220937这样的数字，那么我们申请 $10^{5}$ 大小的数组就不够用了。