1038 统计同成绩学生

本题要求读入 N 名学生的成绩，将获得某一给定分数的学生人数输出。

输入格式：

输入在第 1 行给出不超过 10^5的正整数 N，即学生总人数。随后一行给出 N 名学生的百分制整数成绩，中间以空格分隔。最后一行给出要查询的分数个数 K（不超过 N 的正整数），随后是 K 个分数，中间以空格分隔。

输出格式：

在一行中按查询顺序给出得分等于指定分数的学生人数，中间以空格分隔，但行末不得有多余空格。

输入样例：

10
60 75 90 55 75 99 82 90 75 50
3 75 90 88

输出样例：

3 2 0

思路：

本题题目很简单，但是如果方法不对最后一个测试用例是不可能通过的，一开始我想的方法是定义数组，先将分数存进去，然后将数组排好序，对每一个需要查找的分数进行查找，前三个测试用例很简单就通过了，但是最后一个总是运行超时，一开始想的是排序的方法是不太慢了，更换了快速排序依旧运行超时，后来想的是，查找到一个就删除一个元素，这样以便后面查找更快，但是还是运行超时。苦思冥想下，突然想到，可以直接定义一个101个元素的整型数组，下标对应了分数，直接对这个数组进行统计，然后直接对下标进行查找即可。代码如下：

#include<iostream>

using namespace std;

int main()
{
    int N;
    int score[101] = { 0 };//定义一个存放0-100分的的数组，下标0-100代表着得该分的人的个数
    int temp;
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        scanf("%d", &temp);//根据分数对下标为该分数的人的个数加1
        score[temp]++;
    }
    int K;
    cin >> K;
    for (int i = 0; i < K-1; i++)
    {
        scanf("%d", &temp);//读取下标数据，输出该分数有多少人
        cout << score[temp] << ' ';
    }
    scanf("%d", &temp);
    cout << score[temp] << endl;
    return 0;
}

附上一开始只通过前三个测试用例的代码：

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int find_key(vector<int> a,int key)//定义查找函数对已经排好序的数组进行查找
{
    vector<int>::iterator it;
    it=find(a.begin(),a.end(),key);//找到第一个满足要求的成绩
    if (it == a.end())return 0;//如果没有找到，证明该分数的人为0
    else
    {
        int count = 0;
        for (vector<int> ::iterator p = it; *p == key; p++)//从找到的第一个人开始往后，直到分数不同为止，进行计数
        {
            count++;
        }
        return count;
    }
}

int main()
{
    int N;
    cin >> N;
    vector<int> score;
    int temp;
    for (int i = 0; i < N; i++)
    {
        cin >> temp;
        score.push_back(temp);
    }
    sort(score.begin(), score.end());
    int K;
    cin >> K;
    vector<int> key;
    for (int i = 0; i < K; i++)
    {
        cin >> temp;
        key.push_back(temp);
    }
    int i;
    for ( i= 0; i < K - 1; i++)
    {
        cout << find_key(score, key[i]) << ' ';
    }
    cout << find_key(score, key[i]) << endl;
}

代码：

统计同成绩学生

//1038 统计同成绩学生
//本题简单的可怕...但是一开始没有想到这样的算法导致最后一个运行总是超时，后来换了下面的思路立马就通过了，而且代码也简单了很多
#include<iostream>

using namespace std;

int main()
{
    int N;
    int score[101] = { 0 };//定义一个存放0-100分的的数组，下标0-100代表着得该分的人的个数
    int temp;
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        scanf("%d", &temp);//根据分数对下标为该分数的人的个数加1
        score[temp]++;
    }
    int K;
    cin >> K;
    for (int i = 0; i < K-1; i++)
    {
        scanf("%d", &temp);//读取下标数据，输出该分数有多少人
        cout << score[temp] << ' ';
    }
    scanf("%d", &temp);
    cout << score[temp] << endl;
    return 0;
}

//附上一开始的思路：
/*#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int find_key(vector<int> a,int key)//定义查找函数对已经排好序的数组进行查找
{
    vector<int>::iterator it;
    it=find(a.begin(),a.end(),key);//找到第一个满足要求的成绩
    if (it == a.end())return 0;//如果没有找到，证明该分数的人为0
    else
    {
        int count = 0;
        for (vector<int> ::iterator p = it; *p == key; p++)//从找到的第一个人开始往后，直到分数不同为止，进行计数
        {
            count++;
        }
        return count;
    }
}
int main()
{
    int N;
    cin >> N;
    vector<int> score;
    int temp;
    for (int i = 0; i < N; i++)
    {
        cin >> temp;
        score.push_back(temp);
    }
    sort(score.begin(), score.end());
    int K;
    cin >> K;
    vector<int> key;
    for (int i = 0; i < K; i++)
    {
        cin >> temp;
        key.push_back(temp);
    }
    int i;
    for ( i= 0; i < K - 1; i++)
    {
        cout << find_key(score, key[i]) << ' ';
    }
    cout << find_key(score, key[i]) << endl;
}*/