1038 统计同成绩学生 （20 分）
本题要求读入 N 名学生的成绩，将获得某一给定分数的学生人数输出。
输入格式：
输入在第 1 行给出不超过 105 的正整数 N，即学生总人数。随后一行给出 N 名学生的百分制整数成绩，中间以空格分隔。最后一行给出要查询的分数个数 K（不超过 N 的正整数），随后是 K 个分数，中间以空格分隔。
输出格式：
在一行中按查询顺序给出得分等于指定分数的学生人数，中间以空格分隔，但行末不得有多余空格。
输入样例：
10 60 75 90 55 75 99 82 90 75 50 3 75 90 88
输出样例：
3 2 0
看起来非常简单，就是一个遍历数组的操作。
很容易写出这样的代码
#include<iostream> #include<vector> using namespace std; int main() { int N; cin >> N; vector<int> n(N); for (int i = 0; i < N; i++) cin >> n[i]; int n_score; cin >> n_score; vector<int> score(n_score); vector<int> same_score(n_score); for (int i = 0; i < n_score; i++) cin >> score[i]; for (int i = 0; i < n_score; i++) { for (int j = 0; j < N; j++) { if (score[i] == n[j]) { same_score[i]++; } } } for (int i = 0; i < n_score - 1; i++) cout << same_score[i] << " "; cout << same_score[n_score - 1]; return 0; }
所以，要对遍历进行一些改进。
对成绩进行一次排序，然后查找时只要遇到比自己大的就可以结束遍历了。
这样做确实减少了一些时间，然而还是超时了。
#include<iostream> #include<vector> #include<algorithm> using namespace std; int main() { int N; cin >> N; vector<int> n(N); for (int i = 0; i < N; i++) cin >> n[i]; sort(n.begin(), n.end(),less<int>()); int n_score; cin >> n_score; vector<int> score(n_score); vector<int> same_score(n_score); for (int i = 0; i < n_score; i++) cin >> score[i]; for (int i = 0; i < n_score; i++) { for (int j = 0; j < N; j++) { if (score[i] == n[j]) { same_score[i]++; } if (n[j] > score[i]) break; } } for (int i = 0; i < n_score - 1; i++) cout << same_score[i] << " "; cout << same_score[n_score - 1]; return 0; }
参考了https://www.liuchuo.net/archives/569。
这个代码没有遍历和查找，直接用一个数组same_score(101) 来存放各个成绩(0-100)的人数，然后
读入成绩时直接统计对应成绩的人数（而不是我之前读完全部N个成绩之后再遍历统计）。
#include<iostream> #include<vector> #include<algorithm> using namespace std; int main() { int N; cin >> N; int temp; vector<int> same_score(101); for (int i = 0; i < N; i++) { cin >> temp; same_score[temp]++; } int n_score; cin >> n_score; vector<int> score(n_score); for (int i = 0; i < n_score; i++) cin >> score[i]; for (int i = 0; i < n_score - 1; i++) cout << same_score[score[i] ]<< " "; cout << same_score[score[n_score - 1]]; return 0; }
