1 条题解

  • 0
    @ 2026-11-15 16:40:00

    题目分析

    如果已经分好了队,对于每一队来说,最后吃完的人吃完的时间是

    max⁡i∑j=1iaj+bi\max_{i}\sum_{j=1}^{i}a_j+b_i

    一定是按 bb 降序排序更优,证明如下:

    设 aa 的前缀和为 ss ,假设最后排序方案存在 (i,j)(i,j) ,其中 bi<bj,i<jb_i<b_j,i<j ,那么

    • ii 吃完的时间是 si−1+ai+bis_{i-1}+a_i+b_i
    • jj 吃完的时间是 sj−1+aj+bjs_{j-1}+a_j+b_j

    如果交换 (i,j)(i,j) ,则

    • ii 吃完的时间是 sj−1+ai+bis_{j-1}+a_i+b_i
    • jj 吃完的时间是 si−1+aj+bjs_{i-1}+a_j+b_j

    容易发现前种情况两者取 max 不小于后种情况的两者取 max ,因此交换 (i,j) (i,j) 一定不劣。

    因此,我们将人按照 bb 降序排序,设 fi,jf_{i,j} 表示考虑前 ii 个人,第一队已经分配进去的人 aa 的和是 jj ,转移如下

    $$f_{i,j}=\min(\max(j+b_i,f_{i-1,j}),\max(s_i-j+b_i,f_{i-1,j}))$$

    可以去掉第一维,时间复杂度 O(nV2)O(nV^2) 。

    • 1

    信息

    ID
    133
    时间
    1000ms
    内存
    512MiB
    难度
    4
    标签
    递交数
    1
    已通过
    1
    上传者