##PAT乙级真题 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
本题思路比较简单，可能出问题的就是最后一个测试点咯，嘎嗝我一开始也没过┭┮﹏┭┮
因为题给数据规模了，n<=100000,然后k跟n个规模一样喔。所以用二重循环遍历就会超时了呀，O(nn)大概是100000100000一佰亿了~~~思路：可以用数组，也可以用容器，我是用的数组哈。我先是将待查找的数组进行排序了，复杂度O(nlogn)，然后k大小那个数组不要动，处理不好有可能影响输出顺序。对k大小的数组遍历，寻找每个元素在待查找的数组(已排序)的地方查找。(此时也不能用二重循环，不然又是O(n*n)了)。我想到的是进行二分查找O(logn).那么问题又来了，二分查找只查了一个，简单：（查到后，从mid那里分别往左往右再查呀，目测复杂度O(1)，最后返回查到的个数.实在不明白可以看代码！最后还有总结哦 ，gu~~~lululu) #include <iostream> #include <algorithm> using namespace std; struct cnt { int data; int cnt; }; int Binsearch(int *grade,int low,int high,int x) { int cnt =0; int mid; while(low<=high) { mid = (high+low)/2; if(grade[mid]==x) //核心core ，如果查到就往下看咯 { for(int i=mid;grade[i]==x&&i>=low;i--) //从mid往左查 cnt++; for(int i = mid+1;grade[i]==x&&i<=high;i++)//从mid+1往右查 cnt++; return cnt;//最后就返回了，啥也不做咯，结束此次查找 } else if(grade[mid]>x) high = mid-1; else if(grade[mid]<x) low = mid+1; } return cnt;//否则就返回0 } int main() { int n,k; cin>>n; int grade[100005];//用数组存储 for(int i=1;i<=n;i++) cin>>grade[i]; cin>>k; cnt ji[100005]; for(int i=0;i<k;i++) { int x; cin>>x; ji[i].data = x; ji[i].cnt=0; } sort(grade+1,grade+1+n); //排序 O(nlogn) for(int i=0;i<k;i++) ji[i].cnt = Binsearch(grade,1,n,ji[i].data);//进行二分查找，很重要的一步 for(int i=0;i<k;i++) //最后的输出没毛病~~ { if(i!=k-1) cout<<ji[i].cnt<<" "; else cout<<ji[i].cnt; } return 0; }思路总结： 1.第一步将待查找的数组排序(O(nlogn)) 2.第二步依次二分查找(O(nlogn)) 3.当然就是输出啦 总复杂度O(nlogn)，所以就不会超时啦。 以后碰到超时，就要考虑下是不是需要改进自己的算法啦
