Найдите индексы монстра, который может выжить после игры ⇐ JAVA

[Anonymous]

У меня есть массив целых чисел, значения массива представляют мощность
monster. Монстр может победить другого монстра, если его сила больше
, чем или равна его силе. Когда монстр побеждает другого, победитель набирает силу проигравшего. Если всем монстрам предоставлен шанс
выиграть, найдите нулевой индекс монстров, которые могут выиграть игру, если порядок сражений является оптимальным для этого монстра, и что монстры выигрывают все битвы 50/50.powers = [1, 6, 2, 7, 2]
output = [1,3]
< /code>
Объяснение: < /strong> < /p>
Выбор монстра в индексе 1, обладающий мощностью как 6. Этот монстр может
победить силы [0] и получить свою силу, так что теперь мощность монстра составляет 6+1 =
7. Далее он получает силы монстров в индексе 2 и 4, теперь мощность монстров увеличивается до 7+2+2 = 11, наконец, он может победить монстра в индексе
3, что делает его силу как 11+7 = 18 < /p>
So Monster в Index 1 может выиграть игру. Powers [0],
Powers [2], Powers [4] (поскольку эти значения меньше 7) теперь
Power Monster Power становится 7+1+2+2 = 12, наконец, он может победить монстра в
index 1, что делает его силу как 12+6 = 18 < /p>
so monster at index 3 может выиграть игру. Игра, давайте посмотрим на способности [2], имеющие мощность
as 2. Он может победить монстров в индексах [0] и Powers [4], это
делает силу монстра в индексе 2 как 2+1+2 = 5. Теперь у нас нет
Другие оставшиеся монстры, чья сила меньше 5, так что у монстра
index 2 не может выиграть игру. /> < /blockquote>
Другие примеры, я предоставил как часть основного метода в коде ниже < /p>
Вот мой код: < /p>
import java.util.*;

public class Main
{
public static void main(String[] args) {
System.out.println(solve(Arrays.asList(1, 6, 2, 7, 2))); // Output: [2, 4]
System.out.println(solve(Arrays.asList(4, 1, 2, 5))); // Output: [1, 4]
System.out.println(solve(Arrays.asList(2, 15, 5, 2, 10))); // Output: [2, 5]
System.out.println(solve(Arrays.asList(4,11,8,27,20,3))); // Output: [2, 3, 4, 5]
}

public static List solve(List powers) {
TreeMap map = new TreeMap();
int n = powers.size();
for(int i=0; i key) {
sum += temp.get(key).size() * key;
temp.remove(key);
key = temp.lowerKey((int) sum);
count++;
}
if(count == size) {
result.addAll(map.get(e));
}
}
Collections.sort(result);
return result;
}
}
< /code>
Мой код работает нормально, если размер списка ввода невелик, потому что сложности времени o (n^2 log (n))
он не работает, когда размер ввода велик, как решить это за меньшую времени. < /P. < /p>

Подробнее здесь: https://stackoverflow.com/questions/794 ... ter-a-game