如何最小化机器人全部停机前的总搬运块数（含最终块）？

你指挥一组机器人，每个机器人具备以下属性：

• 每秒可搬运固定数量的块（carry[i]）
• 拥有初始电量（battery[i]）
  你还有一个干扰器，每秒可瞄准一个机器人，使其电量减少k单位。当机器人电量≤0时，停止工作，不再参与块搬运。

每秒流程：

1. 选择一个机器人进行干扰。
2. 所有正常工作的机器人进行块搬运。

目标是选择最优的干扰顺序，最小化机器人全部停机前搬运的总块数（需加上完成任务所需的最后1块）。

示例 #

n = 2
carry = [3, 4]
battery = [4, 6]
k = 3

一种可行策略：

总搬运块数：7+7+3+3+1=21

规则 #

• 每秒只能干扰一个机器人
• 机器人电量≤0时停止工作
• 所有正常工作的机器人每秒都会搬运块
• 所有机器人停机后，必须搬运1块以完成任务

约束条件 #

1 ≤ n ≤ 10^5（机器人数量）
1 ≤ carry[i], battery[i] ≤ 5000
1 ≤ k ≤ 5000

这是一道HackerRank的面试题，无链接可分享。我尝试了如下代码，但仅通过15个测试用例中的5个，其余10个测试用例答案错误：

import java.util.*;

public class Main {
    public static long solve(List<Integer> carry, List<Integer> battery, int k) {
        int n = carry.size();
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int c = carry.get(i);
            int b = battery.get(i);
            int t = (b + k - 1) / k; // 向上取整(b/k)
            list.add(new int[]{c, t});
        }
        
        list.sort((a, b) -> Integer.compare(b[0], a[0]));
        
        long result = 0;
        long currentActiveTime = 0;
        
        for (int[] e : list) {
            currentActiveTime += e[1];
            result += e[0] * currentActiveTime;
        }
        // 加上最终完成块
        result += 1;
        
        return result;
    }

    public static void main(String[] args) {
        System.out.println(solve(Arrays.asList(3, 4), Arrays.asList(4, 6), 3)); // 预期输出21
        
        System.out.println(solve(Arrays.asList(1, 2, 3), Arrays.asList(3, 2, 1), 2)); // 预期输出12
        System.out.println(solve(Arrays.asList(75,45,81,29,2,25,84,56,2,37,39,11,6,68,16,63,49,10,68,80), 
Arrays.asList(26,72,47,97,75,82,17,32,28,57,18,79,40,68,40,93,91,55,31,57), 18)); // 输出错误，当前输出17712
    }
}

我在main方法中添加了部分测试用例及预期答案，其中一个测试用例运行错误：

System.out.println(solve(Arrays.asList(75,45,81,29,2,25,84,56,2,37,39,11,6,68,16,63,49,10,68,80), 
Arrays.asList(26,72,47,97,75,82,17,32,28,57,18,79,40,68,40,93,91,55,31,57), 18)); // 输出错误，当前输出17712

日志中仅能看到输入和输出值，该测试用例的预期输出未知。

问题 #

如何最小化机器人全部停机前搬运的总块数（含最终完成块）？是否存在高效的贪心算法或优先队列解法？

内容的提问来源于stack exchange，提问作者CodeCrusader