1038.同成績の学生を統計する(20)

タイトルリンク:http://www.patest.cn/contests/pat-b-practise/1038
1038.同成績の学生を統計する(20)
時間の制限
250 ms
メモリ制限
65536 kB
コード長制限
8000 B
クイズルーチン
Standard
作成者
CHEN, Yue
本題はN名の学生の成績を読み込んで、ある所定の点数を獲得した学生の人数を出力することを要求する.
入力形式:
1行目に105を超えない正の整数N、すなわち生徒総数を入力する.その後、1行はN人の学生のパーセント制整数成績を与え、中間はスペースで区切られた.最後の1行には、クエリするスコアの数K(Nを超えない正の整数)が与えられ、次いでKのスコアが与えられ、中央はスペースで区切られています.
出力フォーマット:
1行のスコアが指定されたスコアに等しい学生の数をクエリー順に指定します.中間はスペースで区切られますが、行の最後に余分なスペースを指定してはいけません.
サンプルを入力:

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

出力サンプル:

3 2 0

#include <stdio.h>
#define MAX 100000
void Merge(int* data, int* tmp, int left1, int right1, int right2) {
	int left2 = right1 + 1;
	int i = left1, j = left2, k = left1;
	while(i <= right1 && j <= right2)
		if(data[i] <= data[j])
			tmp[k++] = data[i++];
		else
			tmp[k++] = data[j++];
	while(i <= right1)
		tmp[k++] = data[i++];
	while(j <= right2)
		tmp[k++] = data[j++];
	for(k = left1; k <= right2; ++k)
		data[k] = tmp[k];
}
void MSort(int* data, int* tmp, int left, int right) {
	if(left < right) {
		int mid = (left + right) >> 1;
		MSort(data, tmp, left, mid);
		MSort(data, tmp, mid + 1, right);
		Merge(data, tmp, left, mid, right);
	}
}
void MergeSort(int* data, int n) {
	int tmp[MAX] = {};
	MSort(data, tmp, 0, n - 1);
}
int BinarySearch(int* data, int n, int score) {
	int left = 0, right = n - 1;
	int mid = 0;
	while(left <= right) {
		mid = (left + right) >> 1;
		if(score < data[mid])
			right = mid - 1;
		else if(score > data[mid])
			left = mid + 1;
		else
			break;
	}
	int num = 0;
	if(data[mid] == score) {	//        ，              ；    0  
		for(int i = mid; i < n && data[i] == score; ++i)
			++num;
		for(int i = mid - 1; i >= 0 && data[i] == score; --i)
			++num;
	}
	return num;
}
int main() {
	freopen("in", "r", stdin);
	int n;
	scanf("%d", &n);
	int stu[MAX] = {};
	for(int i = 0; i < n; ++i)
		scanf("%d", &stu[i]);
	//        ，             
	MergeSort(stu, n);			//    	
	int k;
	scanf("%d", &k);
	int score[MAX] = {};
	for(int i = 0; i < k; ++i)
		scanf("%d", &score[i]);
	int num[MAX] = {};
	for(int i = 0; i < k; ++i)
		num[i] = BinarySearch(stu, n, score[i]);		//    ，              
	for(int i = 0; i < k; ++i) {
		if(i)
			printf(" ");
		printf("%d", num[i]);
	}
	
	return 0;
}