使用qsort（）进行稳定排序？ [英] Using qsort() for stable sort?

问题描述

我正在尝试解决在线法官系统中的问题： https：/ /acm.cs.nthu.edu.tw/problem/11519/
它需要一个整数n，后跟n行名称和等级。
的问题是使用稳定的排序算法按等级对它们进行排序。
我使用qsort（）并在compar（）中给出该人的订单以稳定qsort（）。这是我的代码：

I was trying to solve a problem in a online judge system: https://acm.cs.nthu.edu.tw/problem/11519/ It takes an integer n, followed with n lines of name and grade. the problem is to sort them out by grades using a stable sort algorithm. I use qsort() and giving the person's order in the compar() to stabilize the qsort(). Here is my code:

class People{
    public:
        char name[11];
        int grade;
        int order;
        void print(){ printf("%s %d\n", name, grade); }
};

int compar(const void *a, const void *b){
    People *A = (People*)a;
    People *B = (People*)b;
    if(A->grade > B->grade) return 1;
    else if(A->grade < B->grade) return -1;
    else if(A->order > B->order) return 1;
    else if(A->order < B->order) return -1;
}

int main(){
    int n;
    scanf("%d", &n);
    People *p = new People[n];
    for(int i=0;i<n;i++){
        scanf("%s %d", p[i].name, &p[i].grade);
        p[i].order = i;
    }
    qsort(p, n, sizeof(People), compar);
    for(int i=0;i<n;i++){
        p[i].print();
    }
}

在我所有的测试案例中，它都可以正常工作问题，但在线法官不断给我提交的四个WA（错误答案）。有人可以给我一些线索吗？非常感谢！

in all of my test cases, it works without any problem, but the online judge keeps giving my submits four WAs(wrong answer). Can someone give me some clues about this? Many thanks!

推荐答案

最后我错过了描述中的一行：

It ends up that I missed a line in the description:

输入包含多个测试用例。在每个测试用例中，第一行包含一个整数N。

The input includes multiple test cases. In each test case, the first line contains one integer N.

经过几种方法，我通过以下代码传递了它： / p>

After several approaches, I got it passed with the following code:

class People{
    public:
        char name[11];
        int grade;
        int order;
        void print(){
            printf("%s %d\n", name, grade);
        }
};

int compar(const void *a, const void *b){
    People *A = (People*)a;
    People *B = (People*)b;
    if(A->grade > B->grade) return 1;
    else if(A->grade < B->grade) return -1;
    else if(A->order > B->order) return 1;
    else if(A->order < B->order) return -1;
    return 0;
}

int main(){
    int n;
    while(scanf("%d", &n)!=EOF){
        People *p = new People[n];
        for(int i=0;i<n;i++){
            scanf("%s %d", p[i].name, &p[i].grade);
            p[i].order = i;
        }
        qsort(p, n, sizeof(People), compar);
        for(int i=0;i<n;i++){
            p[i].print();
        }
        delete[] p;
    }
}

std :: stable_sort可以正常工作，但是收到了TLE（超过时间限制），cin / cout也导致TLE。所以这就是我坚持使用printf / scanf的原因。

std::stable_sort just works, However, it received TLE(Time Limit Exceeded),and the cin/cout causes TLE, too. So that's the reason I stick with printf/scanf.

感谢大家回答这个问题！ ：）

Thanks everyone for answering this question! :)

这篇关于使用qsort（）进行稳定排序？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！