使用qsort（）进行稳定排序？

Z时代
2024-01-10
分类：问答

我正在尝试解决在线裁判系统中的问题：https :

//acm.cs.nthu.edu.tw/problem/11519/

它需要一个整数n，后跟n行名称和等级。问题是使用稳定的排序算法按等级对它们进行排序。我使用qsort（）并在compar（）中给出人的命令以稳定qsort（）。这是我的代码：

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（错误答案）。有人可以给我一些线索吗？非常感谢！

回答：

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

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

经过几种方法，我通过以下代码通过了它：

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;
    }
}