1 solutions

  • 0
    @ 2025-6-17 14:14:03

    操作 1 无需优化,来看操作 2。

    对于操作 2,很容易想到一种基于暴力的优化:

    1、对序列 a 排序。
    2、二分查找第一个大于 0 的数的下标,计为 p。
    3、累加序列 a 中从下标为 p 的数字到最后一个(预处理前缀和)。
    这样优化的时间复杂度最坏为 O(mlogn),空间复杂度为 O(n)。

    注意:

    1、开 long long。
    2、p 要初始化成 n+1(如果没有比 0 大的数就会输出 0)。
    3、本题中所用的前缀和是倒序的。

    • 1

    Information

    ID
    156
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    5
    Tags
    # Submissions
    1
    Accepted
    1
    Uploaded By