使用qsort()进行稳定排序？

Question

我试图解决在线评判系统中的问题: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();
    }
}

在我的所有测试用例中,它没有任何问题,但在线评判一直给我提交四个WAs(错误答案).有人可以给我一些线索吗？非常感谢!

Answer 1

在比较函数中你的意图实际上没有任何问题,使用原始排序将不稳定的排序转换为稳定的排序是完全有效的解决方案.

那么,为什么它被拒绝,我无法确定,至少没有访问使用的测试数据.

这是可能的,该名称可以包含空格,这将搞砸了你的输入法,但(1)似乎并不受测试的描述来表示; (2)它会使输入更加困难,至少在任务目标所针对的水平上是这样.

不过,虽然你可能认为这是不太可能的,还有就是该排序算法可能在某一时刻比较的对象与自身的可能性.这意味着它将返回一些任意值,因为假设它们总是不同的,给定添加的order检查.

您可能应该满足这一点,因为您在比较函数中要遵循的一条规则是一致性,如果那样的a > b话b < a.所以,两个规则,真的:-)

此外,有一件事我会建议为你的遗产-C类的东西尽量少用printf,并scanf在那里C++提供更好的设施.

为此,我相信你会更好:

#include <iostream>
#include <cstdlib>

struct People {
    char name[11];
    int grade;
    int order;
    void print() { std::cout << name << " " << grade << std::endl; }
};

int compar(const void *a, const void *b) {
    People *A = (People*)a;
    People *B = (People*)b;

    // Use grade if different.

    if (A->grade > B->grade) return 1;
    if (A->grade < B->grade) return -1;

    // Otherwise, use order, unique in different objects.

    if (A->order > B->order) return 1;
    if (A->order < B->order) return -1;

    // But cater for the possibility you may compare an object with itself.

    return 0;
}

int main() {
    int n;
    std::cin >> n;

    People *p = new People[n];

    for (int i = 0; i < n; i++) {
        std::cin >> 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();
    }
}

您甚至可能还想考虑远离legacy-C,qsort因为C++提供了内置的稳定排序,特别是stable_sort在<algorithm>.