题解 | #成绩排序#

成绩排序

https://www.nowcoder.com/practice/3f27a0a5a59643a8abf0140b9a8cf1f7

#include <iostream>
#include <algorithm>
using namespace std;

int Partition(int A[], int B[], int low, int high) {
    int pivot = A[low];
    int pivot2 = B[low];

    while (low < high) {
        while (low < high && A[high] >= pivot)     high--;
        A[low] = A[high];
        B[low] = B[high];

        while (low < high && A[low] <= pivot)      low++;
        A[high] = A[low];
        B[high] = B[low];
    }
    A[low] = pivot;
    B[low] = pivot2;
    return low;
}

void Qsort(int A[], int B[], int low, int high) {
    if (low < high) {
        int pivotpos = Partition(A, B, low, high);
        Qsort(A, B, low, pivotpos - 1);
        Qsort(A, B, pivotpos + 1, high);
    }
}

void SameSort(int A[], int B[], int size) {
    int count = 1;
    int current = A[0];
    int start = 0;  //相同成绩区段

    for (int i = 1; i <= size; i++) {
        if (A[i] != current) {
            if (count != 1) sort(B + start, B + i);
            count = 1;
            start = i;
            current = A[i];
        } else count++;
    }
}

int main() {
    int size;  //学生人数
    while (scanf("%d", &size) != EOF) {
        int* sName = new int[size]();
        int* sGrade = new int[size]();
        for (int i = 0; i < size; i++)
            scanf("%d %d", &sName[i], &sGrade[i]);
        Qsort(sGrade, sName, 0, size - 1);
        SameSort(sGrade, sName, size);
        for (int i = 0; i < size; i++)
            printf("%d %d\n", sName[i], sGrade[i]);
        free(sName);
        free(sGrade);
    }
}

全部评论

相关推荐

12-06 20:47
已编辑
复旦大学 C++
华为 终端小艺 定级估计是15a
khj:只要家里条件还行和不愿意太卷真别去华为这种农村做题家云集的地方
点赞 评论 收藏
分享
喜欢走神的孤勇者练习时长两年半:爱华,信华,等华,黑华
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务