首先,每个位置优先选大的,并且每个位置记录一下当前能量值 eie_i ,考虑哪些选B的地方可以反悔,于是开始思考:如果不行,那说明这次修改会使得后面某个位置的能量值小于 hih_i 了,所以只要这次修改不会发生这种情况就能行。也就是说,记当前修改和之前的修改导致能量减少了 EE ,只要不存在 ei−E<hi+1e_i -E < h_{i + 1} ,变形一下 ei−hi+1<Ee_i - h_{i + 1}<E 这次就可以修改,而这些 ei−hi+1e_i - h_{i + 1} 之中最弱的就是最小值,所以建立 chai=mini∈[i,n]{ei−hi+1}cha_i = min_{i ∈ [i,n]}\{e_i - h_{i + 1}\} ,每次决策检查一下 E<=chaiE <= cha_i,如果是就可以改,不是就不行。

时间复杂度 O(n)O (n)

3 条评论

  • @ 2026-10-5 19:52:38

    根据字典序性质,此题不需要反悔贪心,直接贪心,在 b[i]>a[i] 的情况下能选A则就选A即可,从前往后遍历只要能修改那就一定是最优解。 具体做法就是维护两个类似后缀最小值的数组,然后记一个变量,只要当前可以修改那么我永久增加此变量的值,不断判断就行

    ❤️ 3
    • @ 2026-10-5 18:48:38

      qyl,李文越也是有点类似这样做好像。其它人是倒着做

      • @ 2026-10-5 18:44:59

        神秘无解边界卡我一个点

        • 1