1 条题解

  • 0
    @ 2026-11-15 13:13:21

    测试点 1∼2

    从低到高枚举等级暴力搜索即可。

    测试点 3~7

    可以发现如果第一个买的游戏编号是xx,最后一个买的游戏编号是yy,那么能且只能确定从xx到yy之间所有没买的游戏都一定比买了的游戏等级低。

    这样就可以用拓扑排序去做,从能确定的低等级游戏到高等级游戏之间连一条边,每个点的最低等级是所有入度里最高的最低等级加11,最后输出最高的最低等级。

    时间复杂度是O(mn2)O(mn^2)。

    测试点 8~10

    注意到我们的时间复杂度主要体现在建边上,一轮浏览建边需要的时间复杂度就有O(n2)O(n^2)。

    对于每次建边,我们可以建立一个虚点,所有没有被选上的游戏做虚点的入度,选上的游戏做虚点的出度。

    这样一轮连边的时间复杂度为O(n)O(n),总时间复杂度为O(mn),要注意虚点不会增加层数。

    • 1

    信息

    ID
    51
    时间
    1000ms
    内存
    256MiB
    难度
    6
    标签
    递交数
    1
    已通过
    1
    上传者