- 栈
40分,求正解
- @ 2026-2-15 21:03:09
用了C++的 stack 栈,栈上存的是 pair ,表示元素和出现次数,总复杂度 (k是栈的块数)。
这样只过了前两个测试点,其他全 了,求大佬给出正解。
1 comments
-
CYMario 深计硕22 LV 10 SU @ 2026-2-15 23:52:31
纯模拟的期望得分就是 40,考虑一个块数是 的栈每次都插入另一个规模很小的栈中,时间复杂度自然是退化到 的。
因此自然需要想其他的优化方式,包括但不限于:
- 程序内的操作不完全模拟题目,在遇到较大栈向较小栈插入时,在程序操作中反过来,并通过一些建模去等价题目需要的操作
- 采用高级数据结构去优化,直接将操作优化到
- 仔细分析题目本质,可以发现根本不需要暴力合并,因为合并的本质就是序列的收尾相连,自然可以想到链表操作
实现以上任意一种即可通过本题,可以基于以上提示自行查阅相关资料实现~
- 1
Information
- ID
- 25
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 4
- Tags
- # Submissions
- 446
- Accepted
- 31
- Uploaded By