老师想统计学生考试排名，假定一共有n名学生，学号为1至n。现按学号递增顺序给定每个学生的分数，请编写程序，帮助老师计算：对于每个学生，他的成绩比多少人高。假定考试满分为1000分，成绩均为整数。 输入格式: 输入第一行为1个整数n(0<n≤10 5 )，为学生人数。第二行为n个空格间隔的整数a 1 ​ a 2 ​ …a n ​ 表示学号1至n的学生的考试成绩。 输出格式: 输出n个整数b 1 ​ b 2 ​ ... b n ​ ，每个整数后一个空格，b i ​ (1≤i≤n)表示比学生i成绩低的学生人数。

算法1

暴力枚举，对于每个学生i，都遍历一遍成绩数组，计算比他分数低的人数。时间复杂度为O(n^2)，会超时。

算法2

利用计数排序的思想，先对成绩数组进行排序，再遍历一遍，记录每个成绩出现的次数，再计算比当前学生成绩低的人数。时间复杂度为O(n+k)，其中k为成绩的取值范围，本题k=1000，所以时间复杂度为O(n)。

C++ 代码

算法1（超时）

时间复杂度O(n^2)

算法2

时间复杂度O(n)

C++ 代码

相关问题

老师想统计学生考试排名，假定一共有n名学生，学号为1至n。现按学号递增顺序给定每个学生的分数，请编写程序对于每个学生，他的成绩比多少人高。假定考试满分为1000分，成绩均为整数。

输入格式:
输入的第一行包含一个整数n，表示学生的数量。

第二行包含n个整数，用空格分隔，分别表示每个学生的分数。

输出格式:
输出n个整数，用空格分隔，分别表示每个学生有多少个人分数比他高。

输入样例:
5
520 1314 889 666 520

输出样例:
2 1 0 1 2

【说明】
第一个学生的分数为520，有两个人比他分数高（1314和889）；
第二个学生的分数为1314，只有一个人比他分数高（889）；
第三个学生的分数为889，没有人比他分数高；
第四个学生的分数为666，只有一个人比他分数高（889）；
第五个学生的分数为520，有两个人比他分数高（1314和889）。

现有四个班级，每个班级有45名学生，本学期有5门课程考试，，每门课程成绩是百分制。假定每个同学的成绩记录包含：学号、姓名各门课程的成绩共7项，其中学号是一个10位的字符串，每个学生都有唯一的学号，并且这4个班的成绩分别放在4个数组中。 要求利用随机函数编写一个函数给每个学生生成各科考试的成绩（0~100之间的整数），通过调用该函数生成全部学生的成绩 编写计算平均成绩的函数，计算每个同学的平均成绩并保存在成绩数组中 用冒泡排序对四个班级的成绩按照每个同学的平均成绩进行非递增的排序 用选择排序对四个班级的成绩按照每个同学的平均成绩进行非递增的排序 将排序后的每个同学的平均成绩构造一个按所有同学的平均成绩排序的单链表，用C语言编写

好的，下面是一个实现上述功能的示例代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

struct student {
    char id[11];
    char name[20];
    int scores[5];
    float average;
};

void generate_scores(struct student *students, int num_students) {
    srand(time(NULL)); // 设置随机数种子
    for (int i = 0; i < num_students; i++) {
        for (int j = 0; j < 5; j++) {
            students[i].scores[j] = rand() % 101; // 生成0~100之间的随机整数
        }
    }
}

void calculate_average(struct student *students, int num_students) {
    for (int i = 0; i < num_students; i++) {
        int sum = 0;
        for (int j = 0; j < 5; j++) {
            sum += students[i].scores[j];
        }
        students[i].average = (float)sum / 5;
    }
}

void bubble_sort(struct student *students, int num_students) {
    for (int i = 0; i < num_students - 1; i++) {
        for (int j = 0; j < num_students - i - 1; j++) {
            if (students[j].average < students[j + 1].average) {
                struct student temp = students[j];
                students[j] = students[j + 1];
                students[j + 1] = temp;
            }
        }
    }
}

void selection_sort(struct student *students, int num_students) {
    for (int i = 0; i < num_students - 1; i++) {
        int max_index = i;
        for (int j = i + 1; j < num_students; j++) {
            if (students[j].average > students[max_index].average) {
                max_index = j;
            }
        }
        if (max_index != i) {
            struct student temp = students[i];
            students[i] = students[max_index];
            students[max_index] = temp;
        }
    }
}

struct node {
    struct student data;
    struct node *next;
};

void insert_node(struct node **head, struct student data) {
    struct node *new_node = (struct node*)malloc(sizeof(struct node));
    new_node->data = data;
    new_node->next = NULL;
    if (*head == NULL) {
        *head = new_node;
    } else {
        struct node *cur_node = *head;
        struct node *prev_node = NULL;
        while (cur_node != NULL && cur_node->data.average >= data.average) {
            prev_node = cur_node;
            cur_node = cur_node->next;
        }
        if (prev_node == NULL) {
            new_node->next = *head;
            *head = new_node;
        } else {
            prev_node->next = new_node;
            new_node->next = cur_node;
        }
    }
}

void print_list(struct node *head) {
    while (head != NULL) {
        printf("%s %s ", head->data.id, head->data.name);
        for (int i = 0; i < 5; i++) {
            printf("%d ", head->data.scores[i]);
        }
        printf("%.2f\n", head->data.average);
        head = head->next;
    }
}

int main() {
    struct student class1[45];
    struct student class2[45];
    struct student class3[45];
    struct student class4[45];
    generate_scores(class1, 45);
    generate_scores(class2, 45);
    generate_scores(class3, 45);
    generate_scores(class4, 45);
    calculate_average(class1, 45);
    calculate_average(class2, 45);
    calculate_average(class3, 45);
    calculate_average(class4, 45);
    bubble_sort(class1, 45);
    bubble_sort(class2, 45);
    bubble_sort(class3, 45);
    bubble_sort(class4, 45);
    selection_sort(class1, 45);
    selection_sort(class2, 45);
    selection_sort(class3, 45);
    selection_sort(class4, 45);
    struct node *head = NULL;
    for (int i = 0; i < 45; i++) {
        insert_node(&head, class1[i]);
        insert_node(&head, class2[i]);
        insert_node(&head, class3[i]);
        insert_node(&head, class4[i]);
    }
    print_list(head);
    return 0;
}

在上面的示例代码中，我们首先定义了一个`student`结构体，表示一个学生的成绩记录。然后，我们实现了`generate_scores`函数，用于给每个学生生成各科考试的成绩；`calculate_average`函数，用于计算每个学生的平均成绩，并保存在`average`字段中；`bubble_sort`函数和`selection_sort`函数，分别用冒泡排序和选择排序对四个班级的成绩按照每个同学的平均成绩进行非递增的排序；最后，我们定义了一个`node`结构体，表示链表的节点，实现了`insert_node`函数，用于将一个学生的成绩记录插入到按所有同学的平均成绩排序的单链表中；并实现了`print_list`函数，用于输出链表中的所有节点。

在`main`函数中，我们首先创建了四个数组，分别表示四个班级的成绩记录，并用`generate_scores`函数生成了各科考试的成绩；然后，我们用`calculate_average`函数计算了每个学生的平均成绩，并用`bubble_sort`函数和`selection_sort`函数对四个班级的成绩按照每个同学的平均成绩进行非递增的排序；最后，我们创建了一个空链表，并用`insert_node`函数将四个班级中所有学生的成绩记录插入到链表中，并用`print_list`函数输出链表中的所有节点。