Вы командуете командой роботов. Каждый робот: < /p>
может нести определенное количество блоков в секунду (переносить ) < /p>
, имеет батарею с некоторым начальным уровнем (батарея ) < /p>
У вас также есть Zapper, который может нацелиться на одного робота на секунду, снижая батарею на k единиц. Если батарея робота достигает 0 или ниже, она перестает работать и больше не вносит вклад в перевозку блока. Выключите (плюс один последний блок для завершения миссии) сведен к минимуму. < /p>
Example:
n = 2
carry = [3, 4]
battery = [4, 6]
k = 3
One possible strategy:
Time Blocks Carried Zapped Robot New Battery
1 3 + 4 = 7 B 6 → 3
2 3 + 4 = 7 B 3 → 0
3 3 A 4 → 1
4 3 A 1 → -2
5 1 (final) — —
Total blocks carried: 7 + 7 + 3 + 3 + 1 = 21
< /code>
Правила:
Вы можете заполучить один робот в секунду < /p>
Роботы перестают работать, когда батарея ≤ 0 < /p>
Все рабочие роботы несут блоки каждые секунду < /p>
, после того, как все роботы останавливаются, вы должны нести один окончательный блок, чтобы завершить миссию < /p>
< /> < /> 1 ≤ n ≤ 10^5 (number of robots)
1 ≤ carry, battery ≤ 5000
1 ≤ k ≤ 5000
< /code>
Это вопрос собеседования, заданный в Hackerrank, у меня нет ссылки, чтобы поделиться здесь.import java.util.*;
public class Main {
public static long solve(List carry, List battery, int k) {
int n = carry.size();
List 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; // ceil(h / 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;
}
// Add the final concluding point
result += 1;
return result;
}
public static void main(String[] args) {
System.out.println(solve(Arrays.asList(3, 4), Arrays.asList(4, 6), 3)); // Should print 21
System.out.println(solve(Arrays.asList(1, 2, 3), Arrays.asList(3, 2, 1), 2)); // Should print 12
System.out.println(solve(Arrays.asList(1, 10, 1), Arrays.asList(2, 5, 2), 2)); // Should print 40
System.out.println(solve(Arrays.asList(1, 3, 1, 10), Arrays.asList(1, 2, 5, 6), 1)); // Should print 108);
System.out.println(solve(Arrays.asList(1), Arrays.asList(1), 1)); // Should print 2
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)); // wrong output 17712
}
}
< /code>
Я добавил некоторые тестовые примеры в основном методе с ожидаемым ответом, я добавил один пример тестового примера, который не удастся: < /p>
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)); // wrong output 17712
< /code>
В сообщениях журнала я только что нашел входные и выходные значения, но фактический ожидаемый вывод скрыт для этого тестового примера. < /p>
Вопрос:
Как я могу минимизировать общее количество блоков, перенесенных до остановки всех роботов (включая один конечный блок)? Есть ли эффективный подход на основе очередей на жадном или приоритетной очереди?
Подробнее здесь: https://stackoverflow.com/questions/796 ... -shut-down
