Bài toán xếp hạng cho các em học sinh trong lớp bằng C/C++

Bài toán: Lớp học có n học sinh vừa trải qua kỳ thi cuối học kỳ I. Sau khi công bố điểm thi của các học sinh. Giáo viên chủ nhiệm muốn xem thứ tự xếp hạng của mỗi thí sinh.

Giới hạn thời gian : 1 sec.

[Input]

Dữ liệu đầu vào được lưu trong file INPUT.TXT. Dòng đầu chứa số lượng test case. Tiếp theo là danh sách test case.

Dòng đầu theo là số học sinh của hớp. N. ( 10 <= N <= 300000)

Dòng tiếp theo là điểm của các học sinh.Si ( 1 <= ST <= 32000)

[Output]

In ra kết quả ra file OUTPUT.TXT theo mỗi dòng thứ tự xếp hạng của mỗi thí sinh từ 1 cho đến N.

[I/O Example]

Input

2
10
1 2 3 4 5 6 7 8 9 9
10
27 22 15 30 29 12 20 13 6 10

Output

10 9 8 7 6 5 4 3 1 1
3 4 6 1 2 8 5 7 10 9

Chương trình giải:

#include <cstdio>

#include <iostream>

using namespace std;

int N;

int Si[300005];

int ranking[32001];

int repeat[32001];

int maxValue;

int minValue;

int main(int argc, char** argv)

{

 int tc, T, i;

 freopen("INPUT.TXT", "r", stdin);

 freopen("OUTPUT.TXT", "w", stdout);


 cin >> T;

 for (tc = 0; tc < T; tc++)

 {

  cin >> N;

  int rank = 1;

  fill_n(repeat, 32001, 0);

  maxValue = minValue = 0;

  for (i = 1; i <= N; i++) {

   cin >> Si[i];

   repeat[Si[i]]++;

   maxValue = maxValue < Si[i] ? Si[i] : maxValue;

   minValue = minValue < Si[i] ? minValue : Si[i];

  }

  while (maxValue >= minValue){

   if (repeat[maxValue] > 0){

    ranking[maxValue] = rank;

    rank += repeat[maxValue];

   }


   maxValue--;


  }

  for (int i = 1; i <= N; i++){

   cout << ranking[Si[i]] << " ";

  }

  cout << endl;

 }

 return 0;//Your program should return 0 on normal termination.

}