PAT1038 统计同成绩学生 (20分)
本题要求读入 N 名学生的成绩，将获得某一给定分数的学生人数输出。
输入格式：
输入在第 1 行给出不超过 1 的正整数 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<algorithm>
using namespace std;
int main()
{
int n;
while (cin >> n)
{
int* a = new int[n];
for (int i = 0; i < n; i++)
cin >> a[i];
sort(a, a + n);
int m;
cin >>m;
int* b = new int[m];
for (int i = 0; i < m; i++)
cin >> b[i];
int low, mid, high,count;
for (int i = 0; i < m; i++)
{
low = 0; high = n - 1;
count = 0;
while (low <= high)
{
mid = (low + high )/ 2;
if (a[mid] == b[i])
{
count++;
int z = mid - 1;
int t = mid + 1;
while (z>=0&&a[z] == b[i])
{
count++;
z -= 1;
}
while (t<=n-1&&a[t] == b[i])
{
count++;
t += 1;
}
break;
}
else if (a[mid] < b[i])
low = mid + 1;
else
high = mid - 1;
}
if (i != 0)
cout << ' ' << count;
else
cout << count;
}
delete[]a;
delete[]b;
cout << endl;
}
return 0;
} 排序加二分查找，注意不要数组越界，这种解法没有超时， 下一个hash解法在时间复杂度要求比较高的地方可能会超时
#include<iostream>//hash法
using namespace std;
int main()
{
int n;
while (cin >> n)
{
int a[101] = {0};
int x;
while (n--)
{
cin >> x;
a[x]++;
}
int k;
cin >> k;
for(int i=0;i<k;i++)
{
int y;
cin >> y;
if (i != 0)
cout << " " << a[y];
else
cout << a[y];
}
cout << endl;
}
return 0;
} 代码学习笔记 文章被收录于专栏
学习笔记，pat,牛客
深信服三面1人在聊
投递阿里巴巴等公司10个岗位