Помогите с жадным алгоритмом распределения помидоров в кастрюлях [закрыто] ⇐ JAVA

[Anonymous]

Я работаю над заданием по программированию, где мне нужно равномерно распределить помидоры по набору кастрюль. Цель состоит в том, чтобы свести к минимуму количество ходов, необходимых для достижения одинаковых пропорций помидоров в каждом горшке. Однако моя реализация с использованием жадного алгоритма не дает ожидаемых результатов для всех тестовых случаев.
Вот описание проблемы:
У меня есть кухня с 𝑛 кастрюлями, где я одновременно готовлю томатный суп.
Поначалу пропорции помидоров в каждой кастрюле могут быть неодинаковыми.
Цель — определить минимальное количество ходов, необходимое для перемещения помидоров из одной кастрюли до тех пор, пока во всех горшках одинаковое количество помидоров.
Мне нужно использовать технику жадного алгоритма с теоретическим временем выполнения 𝑂(𝑛).
Я реализовал решение на Java, и оно кажется, работает для некоторых тестовых случаев, но не работает для других. Я подозреваю, что в моем коде может быть логическая ошибка.
Вот моя текущая реализация Java:

Код: Выделить всё

public class Tomatoes {
public int minTomatoMoves(int[] pots) {
int totalTomatoes = 0;
int n = pots.length;

// Calculate the total number of tomatoes
for (int tomato : pots) {
totalTomatoes += tomato;
}

// Check if it's possible to distribute the tomatoes evenly
if (totalTomatoes % n != 0) {
return -1; // Not possible to evenly distribute tomatoes
}

int targetTomatoes = totalTomatoes / n; // Target number of tomatoes per pot
int moves = 0;

// Arrays to track deficits and surpluses
int[] deficits = new int[n];
int[] surpluses = new int[n];

// Calculate deficits and surpluses
for (int i = 0; i < n; i++) {
int diff = pots[i] - targetTomatoes;
if (diff < 0) {
deficits[i] = -diff;
} else if (diff > 0) {
surpluses[i] = diff;
}
}

// Distribute surpluses to deficits
for (int i = 0; i < n; i++) {
if (surpluses[i] > 0) {
for (int j = 0; j < n && surpluses[i] > 0; j++) {
if (deficits[j] > 0) {
int transfer = Math.min(surpluses[i], deficits[j]);
surpluses[i] -= transfer;
deficits[j] -= transfer;
moves += transfer;
}
}
}
}

return moves;
}

Может ли кто-нибудь просмотреть мой код и помочь мне определить проблему? Мне нужно убедиться, что алгоритм использует жадный подход и имеет временную сложность 𝑂(𝑛).

Подробнее здесь: https://stackoverflow.com/questions/781 ... oking-pots