每名工程师最多承担一项任务,且同一任务可被多人完成,因此工程师之间互不影响:每名工程师应选择自己能接的任务中收益最大的那一项。
将任务按能力要求 ai 升序排序。从左到右扫描时维护当前已出现的最大收益,得到单调的“能力阈值 → 最大收益”表。对每名工程师的能力 bj,在该表上二分找到 ≤bj 的最大阈值,累加对应收益。
时间复杂度 O((n+m)logn)(排序与二分),空间复杂度 O(n+m)。
数据中心运维平台上有 n 项巡检任务和 m 名值班工程师。第 i 项任务要求能力至少为 ai,每完成一次的收益为 pi;第 j 名工程师的能力为 bj。排班规则是:一名工程师最多承担一项任务,且仅当其能力不低于该任务要求时才能接单;同一项任务可以由多名工程师各自完成一次,该项贡献的收益等于 pi 乘以被完成的次数。
请在上述规则下,计算可获得的最大总收益。
约束:测试组数 T 满足 1≤T≤102,每组 1≤n,m≤10000,同一文件内 n 的总和与 m 的总和均不超过 100000,且 1≤pi,bi≤100000。
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册