快排不是不稳定吗?有没有hack数据?可以看一下对不对吗?

P5740 【深基7.例9】最厉害的学生

Nemonade @ 2021-08-02 17:04:51

RT

大部分题解都用了std::sort,能否被卡掉?

重载运算符写成这样可以避免bug吗?

bool operator <(const node &a,const node &b){
    int x=a.ch+a.ma+a.en,
        y=b.ch+b.ma+b.en;
    if(x!=y) return x>y;
    return a.p<b.p;
}

我太蒻了


by Cat_shao @ 2021-08-02 17:10:18

sort是快排 + 堆排,当快排慢了自动切换堆排


by ud2_ @ 2021-08-02 17:14:50

都不看标题吗?时间复杂度卡不掉,但不稳定性可以卡。

虽然 C++11 起标准规定 std::sort 不能用快排实现。


by UnyieldingTrilobite @ 2021-08-02 18:04:54

@nemonadeMC 现在有了,这题没问题的原理是 n<16,翻下源代码手动模拟一下就会发现这个范围内由于选用的算法的原因不会出问题


|