用了C++的 stack 栈,栈上存的是 pair ,表示元素和出现次数,总复杂度 <=O(mk)<=O(mk)(k是栈的块数)。

这样只过了前两个测试点,其他全 TLETLE 了,求大佬给出正解。

1 comments

  • @ 2026-2-15 23:52:31

    纯模拟的期望得分就是 40,考虑一个块数是 n/2n/2 的栈每次都插入另一个规模很小的栈中,时间复杂度自然是退化到 O(n2)O(n^2) 的。

    因此自然需要想其他的优化方式,包括但不限于:

    1. 程序内的操作不完全模拟题目,在遇到较大栈向较小栈插入时,在程序操作中反过来,并通过一些建模去等价题目需要的操作
    2. 采用高级数据结构去优化,直接将操作优化到 O(nlogn)O(n\log n)
    3. 仔细分析题目本质,可以发现根本不需要暴力合并,因为合并的本质就是序列的收尾相连,自然可以想到链表操作

    实现以上任意一种即可通过本题,可以基于以上提示自行查阅相关资料实现~

    • 1